Only wands and staves do magic (elemental) damage, but those don't fit the Paladin mold. There's no weapon type which does magic (non-elemental) damage, and melee weapons can have small magic damage boosters, but not full magic damage.
In terms of skills, I think you want the Cleric archtype. But that preset starts out with a club, so you might want to go with Fighter (1H sword + shield) or Knight (2H sword), and then change their abilities/skills/stats to match the cleric. Pet Pal is fine to take, it can help you with some quests.