Encounter design / pacing are the problem, not the Paladin class.
I think that what is happening is that a play session and an adventure day are the becoming the same thing more often than not. They are not intended to be. While you perceive that the Paladin is the problem, the adventure day versus challenge is the problem due to the long rest recharge of the Paladin's spell's.
Most of the time they only have one fight per day, and that means the Paladin can go all out with his Divine Smites without caring much for how many spell slots are left, they are lvl 10, so that's a lot of slots to spend.
That ^^ is a symptom of the session and the adventure day matching up.
My sessions have an average time of 3 hours. I try to give a little of
something to everyone every session and make most of the little time
we have, so this means I don't have time to throw encounters at them
just to drain resources.
Sure you do. You can spread out the adventure day over two or three gaming sessions. All of my 5e DM's have done that with some frequency, and so do I. When a session ends (RL is what it is) we note where we are -- "this is a good stopping point, when we pick up next time we will head further down into the Caverns of Calamity ..."
Most of the time they only have one fight per day, and that means the
Paladin can go all out with his Divine Smites without caring much for
how many spell slots are left, they are lvl 10, so that's a lot of
slots to spend. He just takes all the d8s from the table and mows downs whatever is in front of him. Meanwhile, the bard is limited to one spell per turn, and the Ranger and the Rogue can't get anywhere near the paladin's
damage.
Your encounter design is the problem, not the Paladin. You said it yourself: "Most of the time they only have one fight per day." Open the DMG up to the daily XP budget table, dream up three hard-to-deadly encounters that matches roughly that level of XP, and given them that hard to deadly fight each session. Everyone will have to contribute to avoid that third one from being a complete bugger. (And your short rest classes will get to recharge a bit. General idea is that there is no long rest until all three encounters are done.
Or, if you are going to have one encounter for a session, make your encounters fulfill roughly the entire "XP budget" requirement for an adventure day. For three level 10 Adventurers, that amount is: 27,000 XP. Let's look at how we can get 27,000 XP in to one bloody great big battle. (For four, it's 36,000; I just noticed your point on the bard).
CR 9 @ 5,000; CR 10 @ 5,900; CR 11 @ 7,200; CR 12 @ 8,400; CR 13@ 10,000
Three CR 9 Glabrezu give us (5,000 x 3) X2 for number of monsters.
30,000. That's close enough for three. Big fight, tough monsters. And given that there are multiple opponents, none of the party can be slackers for this fight.
Two CR 12 Archmages 8,400 x 2 x 1.5 =25,200. Close. See how it goes. (Spell caster enemies are sorta swingy; saves sway the result)
12-14 Ogres led by an Oni. 12 x 450 + 2900 X 3 (due to numbers) = 24,900 / 27,600. Quantity has a quality all its own. (Granted, fights this big start to get a little unwieldy for the DM ...) 2 Oni + 8 Ogres, while coming it an 23,500, might be less difficult to run); the 2 Oni +9 Ogres comes in at "29,550 so there's sweet spot in there somewhere ... 2 Oni and 12 Ogres comes in at 33, 600 so you are close to what you want for the four person party, including the bard.
Mix and match. If they are handling fights like the above too easily, then ratchet up the difficulty or add some more monsters to each encounter. (The usual caveat about "The CR thing isn't exact science" needs to be included here).
I am not sure if you like AngryGM's web site, but he's got a decent "how to budget encounters" article. (Warning; a bit of language that's sorta harsh there, but it's his schtick). If you have Xanathar's Guide to Everything, the article on encounter building is a nice improvement on what's in the DMG.
This leaves the other players frustrated, as they just feel like they're a lot weaker than the Paladin.
Then make the "adventure day" last for multiple gaming sessions, broken up by a short rest each. That's your core problem: what you have done with your pacing is that most of the time it equates a "gaming session" with an "adventure day." (This is easy to do with outdoor travel phases in an adventure ... in our experience at the tables where I play).
Eventually, the Paladin player had to leave the table and now another new player wants to play a Paladin, and I don't want to repeat that same situation.
Then avoid a one-encounter-adventure-day, or change the challenge.
My solution for this was to limit the Paladin to a single divine smite
per turn, but I don't know how this will affect the class.
Don't fix what isn't broken. Also, take advantage of "short rests." Jeremy Crawford once observed that it is used for pacing the adventure day ... which is your problem.
Example of how to fix your problem.
You can have three hard to deadly fights in "one adventure day." These fights can each take up most of a session. Separate each session with A Short Rest and offer the Long rest after every third session.
Problem solved.
Experience base:
I have a DM who uses a "every four encounters, a long rest" pacing that is nearly perfect, since we never get easy encounters. The pacing is pretty good, as these fights tend to be hard, and we are usually spent by the time we get to a long rest.