Honestly I think the simplest way to combat magic damage for Paladin would be a simple trade off. "Magic sword" ability, you sheathe your shield and use your left hand to perform an incantation to divert a set amount of magical damage to your blade, acting like a lightning rod which helps to absorb the damage you would take from magic and act as a "shield" towards magical damage while leaving you with the inability to block attacks.