Sorry, maybe I'm missing something, but he can teleport as an action (thus, negating the attack) or legendary action (thus, before a character's turn), so he can't attack=>withdraw or teleport. And his regeneration is negated by radiant damage: A lvl 12 paladin always adds radiant damage to his attacks. So best case scenario, he stays away and don't attack, or the paladin or cleric gets him. Sacred flame? He doesn't regenerate Being hit by the paladin? He doesn't regenerate. Different would be if he could teleport as bonus action or reaction. But when he can do so, the damage is already done.
It is the same problem I had with the Balors. The Ancient's paladin eat them alive in no more than 2 rounds, as they dish a humongous quantity of damage with his smite. Misty step allows to pass by the undead and reach the demon easily. Add a rogue, and Moloch can't survive for long. And I have fame for being nasty in combat. I just can't see how he could be a serious threat to a good paladin.
Ok, let's imagine three scenarios. And note, as per the DMG, Legendary actions can only be used by a creature at the END of another creature's turn.
Scenario #1: The paladin is alone, and Moloch is alone. Curiously, this means that Moloch can only use one Legendary action per round (at the end of the paladin's turn). Moloch shows up with a
fly spell in effect. Can the paladin fly? If not, he's in a world of hurt. He's unlikely to ever break Moloch's concentration on the
fly, and Moloch can re-cast it at will anyway. Smites don't usually apply to ranged attacks. Second question: can the paladin cover 120' of distance in a single turn and still melee attack? If not, he's probably dead. Moloch doesn't even need to
fly. He casts
wall of fire at will from 120' away. The paladin closes. Moloch uses a legendary to teleport another 120' back at the end of the paladin's turn. He then casts
wall of fire again. Repeat until paladin is toast. To mix things up, Moloch could use the legendary to cast
stinking cloud after the paladin closes. +3 Con, +5 Cha (aura of protection), no Con save proficiency = 60% chance the paladin loses his next turn. If the paladin fails the save, Moloch gets to pound him with 3 attacks and then repeats with the
stinking cloud at the end of the vomiting paladin's turn. If the paladin ever makes the save, Moloch uses his regular round to teleport away another 120'. If Moloch ever takes serious damage, he uses both the legendary and the regular action to teleport away 120' each. He's now 240' back (and still has the flight option). Once he has distance, he regenerates all damage taken over a few rounds. Then back into the fray. A lone paladin just won't have the mobility to handle a creature that can make an attack and get 120' away every round (and regenerate once it's far enough back to be out of range).
Scenario #2: The paladin has 3 companions (cleric, wizard, rogue). Now, Moloch can use all three of his Legendary actions per round. Moloch can still cast that
wall of fire at will. The combat begins, and the rogue readies an action to fire his bow when an ally gets adjacent. Moloch legendaries to teleport 90' backwards. The wizard gets a spell off, but Moloch has high saves, magic resistance, and legendary resistance. Good luck to him. If the spell somehow got the paladin or cleric much closer to Moloch, he uses a 2nd legendary at the end of the wizard's turn to teleport another 120' back. If not, he uses his 2nd legendary to drop DC 21
stinking cloud on the party. If he manages to take out the paladin for a round, he uses his 3rd legendary at the END of the cleric's turn to teleport back in and prepares to smash him with a full round on his regular turn. When the rogue's turn comes around again, he might cop a sneak attack... but then he teleports another 120' away again. The paladin is never going to get adjacent, and if Moloch ever loses more than 120 HP... he teleports back 120' each on the rogue's/wizard's/paladin's turn with his 3 legendaries. He's now 360' back without even using his own regular round, and begins regenerating.
Scenario #3: Moloch has half a dozen allies. And this is where it gets ugly. Note that Moloch can use his legendaries at the end of another CREATURE'S turn, not necessarily a PC's turn. Monsters, by RAW, all go on the same initiative count if they're the same type. So, Moloch (initiative count 15) is accompanied by 6 random meatshields, all going on initiative count 10. He can now perform all kinds of legendary shenanigans, because he can use all three legendaries on the same count after each one of his bodyguards acts. He can teleport into the party 120' away, whip somebody or try to take a bunch of them out for a round with
stinking cloud, then immediately teleport 120' away again. The PCs don't even get an action off. It gets worse if a PC finished 30' away from Moloch when the triple legendary goes off in his bodyguards's turns. Moloch whips and drags them 30', then teleports 30', then whips and drags them another 30'. He has now separated a PC from the rest of the party by a 60' gap - and can do that every round, without even using his own regular turn. Bad news for the rogue or cleric, neither of whom is going to be making that DC 24 Str save... and they're now out of the paladin's protection aura too.
And, of course, all of this assumes a paladin is present. If there's no paladin, it gets ugly. DC 21
fear breath is going to wreck barbarians, fighters, rogues, etc. Clerics and (some) warlocks can do radiant, but the 120' range of Moloch's at-will
wall of fire is going to be an issue - and neither class is really capable of nova damage. If the party stays grouped, Moloch goes nuts with area effects (
wall of fire, stinking cloud, breath weapon). If they spread out, he teleports 30 ft away from the most remote of them at the end of the 2nd-to-last PC's turn, whips them closer at the end of the last PC's turn, spends his regular turn pounding on them with all three attacks, then teleports away again at the end of the 1st PC's turn. Repeat as required.
