I think they should simply increase the MND of Paladin while equipping the job crystal. That will make Cure better.

Although I would prefer a Paladin-specific Cure spell. How about something that drains MP over time while restoring your HP? MP is only used for Cure.. Stoneskin.. and Flash.. for PLD currently (not going to count the Oaths)