"Heart" might also be the daughter of the honest man, who was kidnapped by someone and the cleric was being told to go see to her rescue and safe return to her father.
Johnathan
His daughter was absolutely the first thing I thought of! This is a good expansion of this idea, and I'd consider working it in to the early part of the campaign. It could either be for the introductory scenario, where the group goes to rescue her, or you could use it as a campaign side-story.
To do a side story, I'd introduce a young girl in the first session. She should be wearing a heart shaped pendant made out of a material suitable for her stations (clay, wood, stone, brass, copper, silver, etc) that her father gave her, but they don't meet him. She should appear to be simply background for the area, so other types of people and items should be noticeable to keep her from standing out. Over the course of the campaign, introduce various "honest" men (ones who appear honest by the PCs perspective), but as the player tries to find his "heart" they keep finding his dishonesty instead. The conclusion can happen in one of two ways
1) PCs rescue the daughter before meeting the father, bringing his heart to him before they even know him. This points out the futility of searching for an honest man, as no man is truly honest (i.e. no one is perfect).
2) The father cannot get anyone to help him rescue his daughter. In the case where help should logically be available, I'd have a changling occur, where everyone else sees his daughter, but he sees a monster. In this case the man should be perfectly honest, an embodiment of the ideal, whom the priest/bbeg is trying to corrupt.