Although some priests are martial, and some paladins are hospitalers. The lines between both classes is somewhat muddled, and different editions (and even different campaign worlds) have treated them in different manners.
Sometimes the Paladin gains their powers from a God.
Sometimes the Paladin gains their powers from their enlightenment, but need a friendly God to cast spells.
Sometimes the Paladin has no need for Gods entirely, and must maintain an Oath. Or not.
Sometimes the Paladin is a knight errant, a champion of the meek and the humble.
Sometimes the Paladin is just an armored brute in the service of a particular religion, be it good or otherwise.
Sometimes the Paladin is one of the Peers of Charlemagne, sometimes they are a Palatine, a chamberlain of the Emperor.
Sometimes the Paladin can lay on hands, is immune to disease, can cast some Cleric spells, and can draw upon the special powers of a holy sword.
Sometimes they can Smite Evil. Sometimes they can't.
Sometimes they can fall from grace and lose their powers. Sometimes they can't.
Ultimately, the question of "what is a paladin?" can only be answered by the DM, who will tell you what a paladin is, in their campaign. I played a Fighter/Priest back in 2e who, by definition, was NOT a Paladin, but you would be hard pressed to tell the difference if they were standing next to a Paladin, and, in some ways, was more effective than one.
By the same token, in a 2e Dragonlance campaign, I played a Lawful Good Cavalier Fighter that my own party thought was a Paladin, to the point they would ask me why I never healed anybody!
Further, not all Church Knights are Paladins either; the Knights of the Elenium are great examples of this. They are pious, stalwart enemies of evil, and trained to wield magic granted to them by a God...but they are also very human, are bound by no oath, and the magic is more arcane than divine, and granted by a Heathen Goddess as opposed to their own God!
The Paladin is an archetype as much as it is a character class- in my opinion, it's someone who has chosen to embody an ideal. And as Superman says in DC Comics Presents #63: