For leveling I'd go retri/ele unless you want to do a lot of instances. In which case you might want to go prot/resto as dps is always easy to find.

You could ofcourse go a middle way by going prot/elemental, which would be considerably nicer concerning group quests.

In any case, I would main the paladin.