Skill issue.
PvP dialogue checks only work on other players if they allow them to, because every player can effectively set the difficulty of the check to "impossible"
This is just how the mechanics are supposed to work, btw. Persuasion checks are rarely supposed to be simple +0 contested rolls. The DM sets the difficulty for NPCs, but only you are supposed to be able to say how difficult it is to persuade your character of something.
Further, even a contested success doesn't always equal a complete success. If the paladin is willing to buy the heart attack story because there's no actual evidence otherwise they might still decide to harbor suspicions that make the next check harder, for example.