Thematically, a Paladin should have access to one or two cantrips, but not at the cost of their fighting style. After all, an Eldritch Knight has access to the excellent Wizard cantrips. If you also pick up Magic Initiate on an EK, you can take a couple of Cleric cantrips which gives the EK extreme combat versatility. Why should a paladin not have access to the same combat versatility as an EK? Isn't it their very job to dispose of the unhallowed?
For example, there is no good reason for a Paladin _not_ to have access to Blade Ward. While Sacred Flame may be redundant given the Paladin's features, a spell like Blade Ward would allow it to better fulfill its role as a frontline fighter.
The only real advantage a Paladin has over an EK as a frontline combatant is its ability to better resist certain types of enemies; even then, those enemies don't always come up which leaves you running short compared to an EK in combat most of the time.