Add More Encounters per Day

Most of the time they only have one fight per day

To me, this seems to be the source of your problem. The DMG recommends multiple encounters per day (DMG p84). As discussed in the "chat" for this answer, one reading of the DMG indicates a recommendation of 6-8 encounters per day of varying difficulty.

This isn't just about play style: having plenty of encounters per day is important for class balancing. For example, the Warlock gets fewer spell slots than other magic users, but this is balanced out by the ability to regain slots during a short rest. Land Druids have a similar ability, one of the few advantages of the subclass over Moon Druids. If there is only one fight per day in your campaign, there is no reason to ever take a short rest - these class features become useless. More martial-reliant classes like the fighter, rogue, and ranger might not be able to dish out the nova damage of more magic-reliant classes, but this is balanced by the fact that they can keep dishing out hurt long after other classes have run out of spell slots - an advantage that disappears if your players only have one encounter per day.

Answer:

You could start individually tinkering with the paladin class to make it fit your style of play better, but neglecting to fix other balancing issues for other classes that are strengthened/weakened by shorter days might lead to issues of fairness. It would be a lot easier and less fraught to increase the number of encounters per day rather than nerfing a class. This solution helps your other players feel more powerful rather than merely making the paladin feel less.

How:

The traditional method for keeping your players from long resting is to add random encounters. Make it unsafe for your players to rest in the wild - taverns exist for a reason! Ask yourself: would you want to sleep outdoors in a world that has heart-eating eagle deers? You can try putting a time crunch on your players' adventures. If someone is paying your party to retrieve an item, they would probably be upset to discover that they are essentially working 1 hour days.

Remember that your players can heal with hit die by taking a short rest.

I understand that your sessions are short, but as mentioned in the comments (and the chat) for this answer, there is nothing unusual about a single in-game day lasting more than one session. Pick up where you left off, and don't let your players rest until they're truly beat!

Even though OP's party does break up the adventuring day into separate sessions. The above advice still stands. The main problem here seems to be the number of encounters per in-game-day; encounters-per-session is just a minor logistical issue.

Consider the "gritty realism" variant resting rules.

Other answers have addressed how balanced your change to the paladin might be. However, it seems likely you have a more general problem with players not really being challenged for their limited-use resources in the way that the game expects they will be - for whatever reason. You could address this by changing the resting mechanics.

In chapter 9 of the DMG, the Dungeon Master's Workshop, there are a variety of variant rules for changing the tone and balance of the game. Specifically, on pg267, there is the Gritty Realism variant resting rule:

This variant uses a short rest of 8 hours and a long rest of 7 days. This puts the brakes on the campaign, requiring the players to carefully judge the benefits and drawbacks of combat. Characters can't afford to engage in too many battles in a row, and all adventuring requires careful planning.

By changing the resting mechanics to take much longer, a few days of adventuring that might previously have been a cakewalk now become a much more strategic affair where the players must carefully balance the resources they use and possibly even pick and choose their battles carefully.

This is a bad idea

As someone who has played and DMed for a lot of paladins, limiting the divine smiting abilities of a paladin substantially reduces the paladin's strengths. Without smiting, the paladin is a class of half-measures: classes like Rogue out-damage it in combat, and the caster classes are far better at spellcasting. Indeed, a single-smiting paladin is almost strictly worse than a Warlock with the Eldritch Smite invocation. Therefore, I suggest a few options:

Be stingy with long rests

The easiest thing to do is just to reduce the number of long rests you give. It's not a big deal to carry over the expended resources over to another session, as long as you can trust your players to accurately keep track of their resources.

By giving long rests less frequently, you can get closer to the originally recommended XP/encounter budgets in the DMG, and force your paladin to ration their smites more carefully. I have observed this even with just two major fights per long rest: my paladin players (and I) can burst down a single big fight pretty easily, but if there are two (or even the expectation of more fights in the same day), then we are much more careful.

Make encounters that can't be resolved by smites

A divine smite is a powerful single-target, melee burst. However, it's not very useful against multiple targets, and it has no ranged capabilities. Thus, paladins are highly optimized against single, huge targets. In order to let your other players shine, you can simply have encounters with many creatures, or at range.

For example, your bard could use Fireball (through magical secrets), which could deal 8d6 to a bunch of enemies at once, or your rogue could constantly drop sneak attacks against enemies from a distance (see here).

As a side benefit, I've found that everyone enjoys combats that are more than just "pump as much damage as possible into this single enemy".

It won't make Paladins much worse

The overall difference this has on Paladins is it makes them somewhat less able to blitz down an especially critical target. Their theoretical maximum damage output is ultimately reduced by 25-50%, depending on whether they save their Smites for crits (to get even more bonus damage) or whether they use them regularly on normal attacks. Most combat encounters don't last a single round, so a Paladin being able to pump out all their damage in one turn is not usually a deciding factor in how the combat resolves.

D&D 5e is not designed around one Combat Encounter per Day/Long Rest

Bluntly speaking, if the Paladin is able to get away with dumping all their spell slots into smites in combat, that tells me that you need to give them more combat encounters in a day. Your problem is that you've created encounters/combats where the Paladin feels no need to conserve resources, so they're burning them with wild abandon. Having more than one combat encounter in a day will solve a lot of these issues by forcing the Paladin to be more judicious in their decisions of when to use their Smites. If they burn all their spell slots in the first combat of the day, and then are all out for each successive combat, they'll quickly learn to be more conservative in their resource usage.

Also consider how your combat encounters are balanced. Speaking from personal experience playing a Paladin, I feel like I get a lot more value from casting Bless on my party, giving everyone significantly improved combat ability, than I gain from using all my slots on Smites. Make sure you create combat encounters where the Paladin can't just solo down their problems.

Change your pacing

...Without changing your story

You actually have a slightly bigger problem than you realize, and it's with more than just the paladin, but it's easy to solve. The classes are balanced against each other around when they each run out of resources (eg hit points, spell slots, etc). This is often referred to as the adventuring day, as explained in the encounter building guidelines in the DMG. The classes with limited but powerful resources are supposed to at least run low on these resources before they get renewed via resting, otherwise the poor rogue will feel very week by comparison, even against a wizard, let alone a paladin. Your story doesn't fit those guidelines, but that's OK.

The DMG also presents a set of variant rules that change the length of rests, and thus their frequency. It presents these rules as making the game more heroic or gritty, but what they are much better at accomplishing is changing the pace of the story. By changing your short rests to 8 hours, and your long rests to 24 hours, you would match the mechanics of the game you want to play (the players all have to actually worry about running out of resources) to the story you want to tell (a number of enemies to defeat that makes sense), based on the details you've given us. See my answer here for an even more extreme solution to a more complicated problem.

Included Encounters that Divine Smite Doesn't Solve

tl;dr Roll with the players and include challenges that are more varied than the combat that suits the paladin instead of nerfing the class.

Sounds like you have a character that is good at front line combat. Penalizing a character for being good at something does not have to be the answer.

Ranged or Animal Encounter to let the Ranger Shine

Design a challenge where the solutions may include manipulating nature, tracking things, and shooting stuff that is difficult to hit.

Skulking and Under the Table Encounters to let the Rogue Shine

A challenge that involves climbing, sneaking, and getting access to restricted areas usually favor a rogue. This is especially the case where brute force will lead to a TPK or break the prize.

Make the Paladin Supplemental to the Others Sometimes

An endless horde of easy, but menacing foes could be added. The paladin's entire job in the challenge is to keep them off of the other characters while they solve the main problem.

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.

After addressing a similar concern elsewhere, here's an alternate solution.

http://www.giantitp.com/forums/showthread.php?567216-For-the-Paladin-what-would-happen-if-I-traded-Divine-Smite-for-spontaneous-casting

My question was related to removing the Divine Smite ability to allow paladins to have all of their spells prepared (effectively replacing Divine Smite with the spell smite spells). While the population found many issues with it, there was one solution that stood out beyond the rest:

Remove Divine Smite, but make smite spells (such as Wrathful Smite) able to be cast after a successful hit.

This imposes the once-a-round event that you're looking for, empowers spell smites for more tactical decision making, makes Charisma more valuable to paladins (so they can prepare more smites), empowers the overall cost-vs-value of the paladins' limited spell slots, and prevents "crit-fishing" (the idea of waiting to crit to spend all of your spell slots on a single Divine Smite "nova").

All in all, it reduces overall damage of your Paladin while increasing tactical decision making. Overall, it makes Paladins more versatile without impacting their power level. A win-win.

Some brief comparisons:

Level 1:

• Divine Smite: 2d8 damage


• Thunderous Smite: 2d6 damage, STR save or prone

Level 2:

• Divine Smite: 3d8 damage


• Branding Smite: 2d6 damage, target sheds light/loses invisibility

Level 3:

• Divine Smite: 4d8 damage


• Blinding Smite: 3d8 damage, CON save or be persistently blinded.

Level 4:

• Divine Smite: 5d8 damage (caps at 5d8)


• Branding Smite: 4d6 damage (upcasted), target sheds light/loses invisibility

Level 5:

• Divine Smite: 5d8 damage (caps at 5d8)


• Banishing Smite: 5d10 damage, banish target with less than 50 health (no save).

This addresses your concern with casting it multiple times and the burst damage, while still making your combat more interesting. Simply limiting the number of Divine Smites being cast will slow the combat down, but won't inherently make the combat more interesting (just more difficult).