Level both, gear both with Allagan/Myth. If you're remotely lucky, you'll have enough Myth leftover and Myth restrictions are going to be lifted in 2.2 anyway with Coil t1-5 unlocked on Duty Finder. I prefer to play Warrior as it's more fun to me but do play Paladin when I feel lazy.