My suggestion is to play both up to 25ish. Start with pld and then do warrior and decide from there.
Just remember, 30 to 40 the warrior has a lot easier time holding aggro. Paladins suffer during those times very heavily.