Play what you're interested in. But if what you are interested in is "complementing the party", as your initial question seems to ask, then I have a couple of suggestions.
First, sans outdoor skills from the ranger, the party seems really lacking. You mentioned a paladin, and focusing on some face skills could work out really well. Rogue-like skills could work well, and there's also no one covering intelligence skills (which could be done well by a cleric of knowledge as well). A bard can cover a good range of skills between expertise and jack of all trades.
Second, I'd be really interested in finding out if the ranger was primarily ranged or melee. If melee then you have two out of four and I'd suggest not going for melee - which would be a slowdown on your paladin thoughts. On the other hand if it's a ranged ranger then a front-liner would be useful, be it a melee character like the paladin or a heavily armored cleric.
Third, they have no healing - is that something you want to cover? (Well, they could have some goodberries going on.) Paladin healing is limited and takes an action - but you could pseudo fit the role with Lay on Hands and the Inspiring Leader feat. Cleric as you mentioned could deal with it as well, but they aren't the only healers. Druids can do decent healing and bards don't suck.
So, for complementing this party, I'd suggest the following to try to hit two or all three of those gaps:
With a ranged ranger
Human variant Paladin with diplomacy skills and the Inspiring Leader feat
Heavily armored cleric
Moon Druid (but watch for skill overlap with the ranger)
With a melee ranger
Bard with some healing and a bunch of skills. Lore might work out better than Valor.
Cleric of Knowledge (or others, that just helps fill in skill gaps)
Ranged Rogue
Druid (but watch for skill overlap with the ranger)
I'm suggesting just from PHB, there are some other options that can fit from other sources as well.