You claim that Clerics feels more Paladin bcs they have deity ... What difference would there be between Clerics and Paladins, if they would have them aswell?
It's a small difference. I think of it like a Cleric is a believer in their God while a paladin has devoted their whole life to the God. For a real life example. The Christian you see preaching on a street corner would be a Cleric. While the Priest or Nun would be a Paladin.
I don't know if this has been said yet on this thread, for it is too long to read everything, but I think your concept of paladins is a bit off.
Cleric = Priest Paladin = Knight
Though knights often fight for a church, they often fight for rulers, ideals, etc.