Benjamin Olson
Hero
If you are afraid they are too melee heavy for a Paladin, consider one of the other charisma classes. Both charisma duties and arcane spell duties seem to be unaddressed by the current party composition, and while it's not the most politics and persuasion heavy campaign, it's also not the least.
I would also consider Wizard, given that the party does not have any arcane magic, probably doesn't have anyone particularly good at knowledge checks, and that the adventure does have several opportunities to learn substantial numbers of spells.
I would also consider Wizard, given that the party does not have any arcane magic, probably doesn't have anyone particularly good at knowledge checks, and that the adventure does have several opportunities to learn substantial numbers of spells.