I don't want any mechanical answers about being a full caster vs half caster and the like.  I am hoping to develop a better idea of what role a Cleric or Paladin would play in society as a whole rather than at the party. 

In my world, each god (Dawn War Pantheon) has only a single Cleric and a single Paladin. They act as spiritual leaders for the followers of that faith and sometimes find themselves as political leaders, generals, monarchs, or even folk heroes as well.  I am looking for advice on ways of making them seem more like two different jobs and less like two of the same. 

In General Terms

• I use phrases like the "The Left Hand of the Devine" referring to the Cleric, as this hand would typically hold the Shield. Clerics roles would be to help protect the faith from within. Im trying to make this feel more like a "Church" leader. 
• I use the phrase "The Right hand of the Devine" when referring to the Paladin, as this would typically hold the sword. Paladins are more military or political leaders and who are concerned with spreading the faith and are actively trying to more actively follow the god's tenants. 

Any Advice? 

Clerics have their powers granted to them via worship and good faith. Paladins swear an oath to their god and gain powers as long as they uphold that oath. Overall, yes, clerics are more based around faith, followers, and church stuff, while paladins are more into smiting the unbelievers, burning the heretics, et cetera. Fun stuff.

One of the small changes I do is disallow Paladins from using Ceremony.  Battlefield funerals are very nice, very "now his watch has ended", but weddings, britot, baptisms, bar mitzvahs, leading daily prayers, conferring holy orders on an initiate, funerals, all that stuff is the absolute purview of clerics.

Now, in your D&D game there probably won't be much opportunity or desire to have paladins playing deacon or have clerics getting into a turf war with them over who gets to be the mohel.  So let's think of it this way.  The archetypical D&D cleric is Charlton Heston in The Ten Commandments or Jeffrey Hunter in King of Kings.  Not actual religious figures, but the Hollywood version thereof.  The archetypical D&D paladin is Sir Galahad who has the strength of ten because his heart is pure.

In the setup you describe, where there are only two, the relationship would probably look like Moses and Joshua in the movie, where one is both the religious and the political leader and the other is his lieutenant who assumes leadership when the cleric is absent (like when Moses can't get into the Promised Land).

I guess, to make a long story short, I think you have the roles backwards.  The cleric has to be the political leader and the paladin has to be subordinate to them.  I think you could have a situation where one person serves BOTH roles, like Muhammad, but I don't see what the priest would do in the secondary role.

Clerics work directly for gods, at least in most campaign settings.  Paladins, in 5E, are more committed to ideals and don't have to follow a particular god (though they often do).

Clerics convert followers through the use of the Word.

Paladins convert followers by bringing the sword.  They probably don't convert many of their "victims" but maybe a few onlookers get the message and drink the Cool-Aid.