If you are boosting the pally, it doesn't matter. You're leveling the paladin, you shouldn't need any help. If you DO need help, spec it holy and have it spam heals on you. If you don't need help (which is more appropriate) spec it prot so it can take a few hits if something goes wrong.

If you're using the pally to boost someone else, definitely go prot. See my video if you haven't already.