AoE Prot Pally is actually really fun at level 40 when you get seal of wisdom and plate. You can run around, gather up 5 or so mobs and aoe them down, no problem. Even before that you can smoke the murloc camps outside of Menethil harbour. Basically any mobs that just melee
Just go holy to consecration then head into prot from there
Prot pally is definitely more fun than prot Warrior solo