Mediaeval bishops are the equivalent of nobles in rank and influence (hence the investiture controversy). And in AD&D clerics can be nobles - the paladin class description says that "paladins will take service or form an alliance with lawful good characters, whether players or not, who are clerics or fighters (of noble status)" (PHB p 24).
But more generally, nothing about the cleric as a class tells us that the character has a differenet relationship either to the divine, or to temporal aspects of life, than does the paladin. A particular table could of course play it that way if they wanted to, but it's not implicit in the classes. And while in play a thief is obviously different from a fighter (different armour, different skill set) and a MU is obviously even more different from both of them, in play a cleric and a paladin do the same sorts of things, make the same sorts of contributions: they fight, they provide healing, they detect and ward off evil. Of course a player who chooses one rather than the other is making a mechanical choice to emphasise one or another of those things (better turning and healing as a cleric, better fighting as a paladin), but again that's about implementation, not theme/archetype.
In Medieval times there were simple Nobility (Fighters), Knights or those Holy Knights that were either anointed or ordained by the Church (Paladins), and the Priests. Among Priests there were the normal every day priest and then there were the Landowners (Clerics). These Landowners were NOT knights, though they may be nobility by birth. In many instances a second son would be sent to the Church for "safekeeping" but if the eldest died...they then would be called for. They had combat training and were typically very able warriors.
They had NO HEREDITARY LANDS. The lands that they watched or governed were owned and regulated by the Church. The church (in this instance, in Europe it was normally the Catholic Church, but in Britain this changed later on) controlled a GREAT DEAL of land, much like nobility did, but they were owned in the name of the church. Thus, a Bishop could very well be acting in the same role as a Knight, but in this instance they would be as a representative as the Church. They would be the church's governance over the lands. However, the lands were NOT theirs or their families, it was the church's land.
This was different than the landed Nobility. This land was THEIRS as given to them to control by the ruler of the Kingdom/Empire/etc. Their lands were hereditary and thus control of the land went from Father to Son. AS long as they were anointed and condoned by the Church, they were considered Holy under that idea.
Thus...the Bishop of Paris and it's adjoining areas would go out to the varous fields that the Church controlled to ensure that the Clergy were drawing the taxes and other such items from those lands. If the Bishop was excommunicated, they would no longer have that power. The control of taxes and tithes would be given to another. Their control and power was tied up to their loyalty to the church.
On the otherhand, a Knight, who separated from the Church or was excommunicated did NOT necessarily lose their lands. They may be attacked because they were then heretics/apostates or otherwise seen as their lands were attempted to be taken, but they did not necessarily lose their rights to the land and power due to excommunication.
Hence, the Bishop in Charlemagne's story would be the typical D&D Cleric. He went out in full armor. He battled. He swung his mace. He fought alongside the soldiers and was obviously of high rank in consideration to that.
On the otherhand, Charlemagne would be the archtypical Paladin. He owed no land allegiance to a Church and even if not appointed he would still be King. However, he was (some would say he forced this from Rome) appointed and anointed as the Holy Roman Emperor, Defender of the Faith, Defender of the church, etc...etc...etc.
Frederick would be a prime example of a King who was a Fallen Paladin (excommunicated from the Church, then went on Crusade and probably had the most success one could hope for) who then atoned in AD&D terms...fell again...atoned again....etc...etc...etc.
There is a clear delineation which those from Gygax's generation could understand each and how they were different. It's based on the mythology and legends one learned in school (not sure if they teach this stuff in school anymore, TBH).
They may seem similar, but there is a WORLD of difference.
Basically, a Paladin is a Knight. If one really is looking for the difference between a Knight and a Paladin there is very little difference, except one is anointed or approved of by the Church, and the other may or may not be. They are the Kings, the Dukes, the Lords, the Nobles.
On the otherhand, a Cleric is specifically a Warrior FOR the Church. They are part of the Church hierarchy, but even moreso, are trained and ready to battle and defend the Church and it's lands. They are the Cardinals, the Arch-Bishops and the Bishops (Priests and local clergy on the otherhand may or may not be...they may not have any martial training or expectations to go to battle or control lands and areas). Traditionally before modern times, these guys often WERE Warriors, just as much as any of the nobility, but they were under the CHURCH in doing so, not a King (though even that could get murky in history).
Think a Chess board. You have the Bishops which are very different than the Knights and the King. They are different pieces and are able to do different things.
Granted, I think this came into a clearer and stronger focus in AD&D than OD&D (in OD&D, I think it was expected that one could understand the difference, but it is not necessarily spelled out and so could be muddled), but I think that it is pretty clear on what the difference was in regards to middle 20th century education.