Okay, so nobody's tackled this one, so I'm going to give it ago. This is not the latest scholarship, so hopefully a proper classicist can swoop in to fix it.

The biggest thing to remember here is that Greco-Roman religion was mainly thought of what scholars of religion call ordopraxy rather than orthodoxy. A Greek or a Roman doesn't really care whether you believe certain things about, say, whether Hephaestus has a club foot or Aphrodite intervened in the Trojan War to protect Aeneas from Diomedes. After all, Greco-Roman myths are just that: mythoi, stories. What they care about is eusebeia, i.e., piety. What does a good citizen do? He makes his sacrifices, takes part in various rituals, etc.

This is the reason that the Interpretatio Romana works so well. Gauls sacrifice to a god named Cosus who has features that are like the features of the God the Romans sacrifice to that's called Mars? Great, change the name plate on the temple, give it some columns, and everyone's still practicing their pietas (Latin for eusebeia).

There is, fwiw, a reading of the Interpretatio that says that it's fundamentally an exercise of power by Rome over conquered people.

So Romans are cool with most religious practice because if you're practicing religion, you're being pious, a good member of the community. There are some exceptions, but a religion has to be particularly freaky or anti-Roman for the Romans to not just hoover it up into the Interpretatio.

But...

By the time the Judaeans have emerged from the Babylonian Captivity and built the Second Temple, their faith is monotheistic. How this occurred -- and there's some scholarship suggesting that prior to the exile or at least the reforms of Josiah that the Hebrew religion may have been less monotheistic -- is a bit beyond the remit of a post I already don't have much business making. But monotheistic it was, with the strict requirement that Jews worship no God but The Lord God of Israel (by the Second Temple they've already quit pronouncing Yahweh aloud).

So they're Roman clients first and then eventually incorporated into Rome altogether. Now then, no Jew would allow the Interpretatio for Judaism. You're not going to assimilate the Lord God of Israel into Zeus. The Romans find this... weird, since they don't really have the notion of an exclusive religion. But they acknowledge that Judaism is old and has a tradition behind it, so they (sort of) allow it. Pontius Pilate was as brutal as any Roman governor, but after a lengthy bit of wrangling with Judaean leaders, he removed some Roman standards in Jerusalem that the Jewish people considered idolatrous.

But then, we start to see an offshoot of Second Temple Judaism, namely Christianity. And this is a problem. Why is Christianity a problem for Rome? Well, Christians don't take part in the worship of their community's gods: they're offending pietas. Indeed, one accusation leveled against Christians is that they're "atheists." Various communities in Rome have the biggest problem with Christianity when it comes to the fact that it's members will shun what seems like a basic function of community life.

But... In 313, Roman Emperor Constantine legalizes Christianity and begins favoring it. The Roman state still supports the old gods as well, but now Christians enjoy the favor of the Emperor. From now on, all emperors but Julian the Apostate (r. 361-3) would be Christian. Plenty of Romans hold to the Old Gods, and although the Senatorial class is largely pagan, what we might call an "upper-middle class," elites, but not elites with empire-wide landholdings, start going Christian fairly quickly. By the rule of Theodosius I (r. 379-95), you see the end of state support for the Old Gods and laws to end things like animal sacrifice, etc. Theodosius's rule is generally regarded as the time that Rome is officially Christian.

The short answer to your question is that once Christianity, which maintained Second Temple Judaism's exclusivist approach, finds its way into the Roman state, well, eventually that religiously exclusive vision will triumph. When the Western Roman Empire breaks into different kingdoms, that's also the end of the power of the super-rich Senatorial elite, the last real bastion of paganism.

In the successor kingdoms to Rome in Western Europe, the Christian faithful take a strategy of converting the kings of the peoples who had established these kingdoms. And once a king declares that his people will be baptized, well, that also encompasses an outlawing of worship of the Old Gods.

Okay, this is a bit of a low-effort post, but it's a beginning until a classicist can come in with something better.

Did this answer make sense?