There is a major definition problem here.
The cultures you reference did not draw a distinction between church and state. To refuse to offer incense to the patron god of the state was to refuse the legitimacy of the state. One metaphor might be that to refuse incense was like refusing to pay taxes - god and the state deserved their due.
In general, these polytheistic cultures didn't care who you worshipped, but they did care if you openly and publicly denied that the patron god existed - that was an act of civil disobedience that no society could ignore.
The intolerance wasn't the polytheists, it was the primitive Christians, who refused to acknowledge that their neighbor's worship & participation in the state was legitimate. Primitive Christians denied public ritual, and refused to participate in communal government driven activities. That intolerance escalated to civil punishment.
SideNote: it is inaccurate to call state sponsored religion "pagan" - pagan religion connotes rural/uncultured religious ritual.
Aside: THere is a good presentation of a related question,
Did the Great Heathen Army persecute Christians; different era, different polytheistic pantheon, but the same confusion over the concept of tolerance.
Update
To answer your question If they "did not draw a distinction between church and state," that would also seem to imply that the state was a god. Is that true? the answer is no. le etat cest moi per Louis XIV may be the appropriate analogy once emperors became the norm. "The state" as we came to know it in the post enlightenment wasn't quite it. And in the case of Rome, once Julius Caesar and the Imperial age overtook the Republic for good, the linkage between the Emperor and the State became more pronounced.
That is a reasonably subtle question, and deserves an answer that is both better reasoned and better researched than I'm capable of (particularly at this moment). I think that they would generally disagree that the state was a god, but that they would agree that the state could only survive with the active cooperation & sponsorship of a god. I think that 95% of the population would agree that gods controlled the unseen forces that were responsible for the success or failure of anything beyond human control. Every state/polis/civic entity/institution was sponsored by a god. The institution flourished with the god's favor and suffered for the god's ire.
I'm going to draw a broad analogy here - this will not hold up for analysis, and in no way do I mean to disrespect, but imagine that there were an ethnic group in modern day america that refused to say the pledge of allegiance, to pay normal deference to the flag, refused to participate in judicial proceedings because they included the flag, refused to enter public buildings that displayed the flag, refused to send their children to public schools (because the school displays the flag). This group would not, under penalty of prosecution, perform even the most minimal acts of respect for the flag (standing, saluting, etc.) Imagine that they rejected the compromises of groups like the Jehovah's Witnesses who find compromise positions that endorse the state while rejecting the practices that they find idolatrous. Such a group would be subject to a great deal of scrutiny to try to understand their contempt for our shared symbol. THe early Christians rejected the civic symbols of their neighbors - they went even further and asserted that respect for national symbols was idolatrous and sinful and imperiled the eternal soul.
Like I said, this is not a precise metaphor - nobody today believes that the flag's happiness is required for national prosperity. But if such a group existed (and I am not interested in examples or counterexamples), they would be the intolerant ones, not the flag wavers.
This is veering away from history rapidly.