Conservatives Set to Win Majority
is a shortened form of
Conservatives Are Set to Win A Majority
It's a state of being; "the Conservatives" is not the subject of "set" here, and "set to win (a) majority" is an adjective phrase here.
So, it's not technically a grammatical sentence, but newspaper headlines can omit words in stereotyped, recognizable ways and it sounds OK in that context. No one would say this in conversation! But it actually signals that you're quoting a newspaper headline.
Therefore, the second of your two readings is correct here!
(It's also totally OK to use full sentences in headlines - this sort of thing is a style that was developed when block printing was the current technology and it cost more money to print a paper with more letters!)