[BarackObooma]

Paladin's require you to gain 40% more experience to level which could really have you pulling your hair out.

I'd say stick with the Cleric and try to group/duo. You can solo but it will take longer.