3 paladins, 6 players, what's the other 3?
Any fireballs?
A mob of smaller enemies could give a bit of work to paladins, between raw numbers and pack tactics or stuff like that.
Running hordes by Sly Flourish might help keep it reasonably flowing: https://slyflourish.com/running_hordes.html
Even if they get fireballed, at least those characters get to shine for once.

Keep in mind that you, as a DM, "win" whenever everyone's having fun, not when you beat them.
That said, it sure is fun for everyone when you give them a challenge.

You can also put pressure on them indirectly.
If they're so fearful, maybe the monsters just avoid them so they can focus on easier pickings.
Their martial prowess is unmatched, sure, but how do the bad guys deal with it?
Maybe the bbeg sacrifices fodder to occupy the party to buy themselves time to focus on whatever ritual or macguffin.
Even goblins could overwhelm them eventually, given the numbers. A hundred? A thousand?

Also, the party can't be everywhere at once.
The ones occupying the PCs die just fine, but the other hundred still ransacked the town.
Whether the PCs crush the monsters might not matter to your bbeg if they can just delay them long enough to accomplish their goals.
Maybe the bbeg has a doppelganger win their trust or manipulates them somehow.

Mechanically, your paladins probably dumped dex or int. Feeblemind, Enemies Abound, Mebtal Prison, Synaptic Static or even Mind Sliver could be annoying.
But then, is it fun? Idk.
A few mindflayers ambushing them, or maybe a vampire turning a beloved NPC.
If you can't challenge their martial prowess, challenge their morals.
Will the party keep messing with the bbeg plans, or will they focus their efforts on saving that npc, buying the bbeg time.

Maybe a one way portal can spice things up more than a bag of hp or a save-or-suck effect.
Idk

Maybe use more weaker enemies? They might be able to deal a lot of damage in one turn but its across relatively few enemies. Rather than trying to increase the difficulty of one or two enemies in combat, provide a larger number of weaker ones.

This would mean,

1. They either “waste” large amounts of damage overkilling a weak enemy
2. Hold back their smites etc to not “waste” it on a small enemy
3. More enemies than they have combat actions starts to allow for enemies to have a turn at hitting them

You can of course include some beefier enemies as well.

Does the party just brute force into combat, smashing everything they can see without thought? Throw in some hidden enemies, ambush them if they aren’t checking for possible ambushes

Wow that does sound like a challenge to balance for! Here's a few things to keep in mind.

1. A larger group of players is usually going to need more enemies for any given combat to be challenging. If you're using a prewritten adventure or an encounter builder of some sort, consider bumping up the number of monsters a little.

2. Consider alternate objectives/fail states. This can take some creativity to pull off, but introducing something like hostages in danger, or a thief trying to carry away some of the party's loot during combat can make things much more interesting. This can be especially effective with paladins, when what their oath says they should do conflicts with the tactically correct move.

3. When they can, enemies will want to create advantage before the fight even starts. Letting the players into sticky webs, slippery floors, or a prepared portcullis can restrict their movement and create openings to attack. They might also try to break or disarm weapons or shields when they see the paladins are hard to hit head on.

4. It's good for the players to feel powerful! Most encounters should be challenging, and the players should occasionally be pushed to their limits in a boss fight, but a few cakewalk encounters are good to have too. They're especially good when they're similar to a fight the players had a lot of trouble with 3 or 4 levels ago to highlight just how strong the characters have become.

Wait, so you're DMing for a party of 3 paladins, a cleric, a ranger, and a warlock? o_0

Have you considered an anti-magic field area of considerable size? That's hardly a good continual response but it may allow a more challenging encounter, especially if the field can be briefly turned off by characters expending spell slots into a single dangerous spot while being attacked. Since it prevents Divine smites and the bonuses. (Someone could 5e-argue that probably, since its pretty nonsensical with class abilities at times but I'd just overrule it.) You can even use it with Mindflayers or other psionic aberrations, since arguably their abilities can still work if you rule they can. (Psionics don't necessarily equal magic unless you set some other precedent.)

Other concepts are to add hazards and chaos causers to battlefields. Floating clouds of glittering fog that reflect spells to random other targets, negative-energy/undead quicksand bogs that leech endurance instead of doing damage (and whose saves are to avoid getting stuck not to avoid the drain), unsteady floors to drop out and separate parts of the party, or lair effects that randomly teleport characters back to earlier areas of a dungeon, forcing them to run back through to get back into the fight (don't overuse that one but if there are traps earlier its a great way to force them to ignore traps in their rush).

Also just tasks to do while being attacked. The paladins + cleric can defend well together but force them to be separated into different regions doing a task and you up the tension (even if you don't up the danger).

You can also try bringing forward older monsters that undercut benefits/items. Black Puddings, Rust Monsters (Or their papa Annihilators), or port over other monsters like Magerippers or Spellweavers from 3.5.

Traps can also be good, since they may be taking 1/4 damage on a save, but if the traps also cause inconveniences or force them through alternate, and slowly more damaging paths (like crawling through a stone brambled tunnel instead of taking the other tunnel because it caved in and almost crushed them), they can still build up and be valuable.

Also if they're incredibly proficient in combat, the enemies probably know that by this level. So you might have to start attacking them legally or socially, depending on the situation. Or just start having foes avoid them. Make them burn resources to set up engagements where foes can't run or attack them when they're on their back foot relaxing with assassins in the bathrooms, poisons in the bar bread, false accusers of horrible crimes on the streets and in court. (Depending on who their foes are of course.) You do that so that their character get paranoid. Start trading things like spell slots, the benefits of sleep, or close allies to try and defend themselves, so that they're weakened before they even touch something like a dungeon. If they party is just too invincible in combat as it is, don't just attack them there, let them know that existence is sortof a threat. (And as before, how much you use it is important an should be informed by session 0. You want them tense and excited, not miserable, and "the world as the DM's weapon" isn't necessarily the right way to approach it but its a nice tool to have in the chest. Hammer finds nail and all that.)

I would use attrition. They have 7 spell slots. If they spend 2 of those per encounter, force them to have 4 encounters before they can long rest.

First warn them. Give then a hint that the dungeon is large and will mean quite some time without resting.

Then bait them. For example: an undead unit that has resistences against physical attacks, and does little damage, or is very easy to run away from. Maybe an undead slime blob or gas thing? E.g. https://www.dandwiki.com/wiki/Gas_Wisp_(5e_Creature) They may use their spell slots on divine smites to deal radiant damage. Even though there are plenty of other options in the arsenals of the other 3 players.

Or create a dungeon that forces them to split the party to progress, allowing them to reunite during or after the battle. This could give you several turns where you can exploit the weaknesses of a divided group.