Not only is that not true for America but the bit in bold is actually absurdly false. The earliest Islamic conquistadors actually discouraged conversions among the conquered and regularly tried to maintain good relations with people of the book (i.e. Christians and Jews), certainly far more so than their Christian contemporaries (consider the history of the Jews in Spain, Moorish rule, while certainly sectarian and frequently bigoted, was bookmarked between two extremely anti-Semitic states of Spain under the Visigoths and the Spain of Ferdinand and Isabella, the latter of which expelled all the Jews from its territory almost immediately after the defeating the last Islamic Kingdom on the peninsula). The Islamization of what is now the 'Arab World' was a very slow process and not even complete today when Arab Christians and the Yazidi frequently appear in the news. I have, for example, seen the period after the Mongol Conquests cited as for when Syria first achieved an Islamic majority.
While Al's point is important, I want to mention as a something towards an answer to this question the power of states and the power of religious infrastructure. Centralized states from the Early Medieval period onwards until very recently regularly enforced conformity of their institutions with one or other religious code. This meant to get anywhere in the top layer of society where there was centralized power one had to conform and belong into the religious beliefs of that society. In this sense it didn't matter what the
hoi polloi were (and throughout this whole period the extent to which they were 'non-Pagan' is questionable as far as that question is meaningful), the levers of power were headed by institutions which promoted one doctrine above all, and those who objected were, at best, suspect. Furthermore, powerful states like the Byzantines, the Franks, the Abbasids, and, later on, the Spanish and the Safavids could and did conquer large territories upon which they could impose their doctrines. Finally on this point, other 'Pagan' states frequently looked to the powerful centralized states and their ruling classes, seeing them as examples to emulate, took up and borrowed many aspects of those states, including their religious doctrines. In Europe there was the conversion of Kievan Rus and Bulgaria to Orthodoxy by rulers wishing to copy the Byzantines and the final state (note: I say state) to convert was Lithuania at the end of the 14th Century after the marriage of its King to the Queen of Poland. Lithuania was the more powerful state of the two but there was no question of Poland converting to paganism for many reasons (one very important such thing is that Pagans rarely did 'conversions') as Poland was connected to a vast European social network - 'Christendom' - while Lithuania was an isolated state surrounded by the culturally hostile. Around the world, leaders converted as they could tap into social networks of immense power; the conversion of the Malays and Indonesian to Islam was part of this process. This should not be read that their motives in converting were mercenary and did not 'really' convert only that their conversion was seen as by them as a project of cultural affiliation towards more powerful (whether in terms of political or social power) groups.
This brings me onto my second point, religious infrastructure. Across a wide area where there was one dominant religion there was a conformity of structures relating to religion. Despite being in different states the Catholic church in Toledo and the Catholic church in Warsaw were part of a single organization with a single structure which used the same language and had the same prayers and the same (or almost the same) intellectual rhetoric and assumptions. The same was true for Mosques (although obviously power was not quite so formalized as it was in the RCC) across the Arab World and I guess, although here I know much less and there was more local variation, Buddhist Monasteries across South and East Asia. This conformism is one of the reasons why issues around heresy were so important, it threatened the unity of the unified body by its clash of differing doctrines and practices (and frequently languages and organizational structure). Churches, Mosques, and Monasteries were very powerful bodies who were the center of the community and were, in a lot of this period, the best schools around. It is notable how in Early Medieval Europe how much literacy only really appears when Christianity arrives, especially in the regions that were never part of the Roman Empire like the East or Ireland. The spread of the Arab conquests allowed a single form of cultural expression to dominate across North Africa and the Middle East. To leaders and upper classes (in the 'Arab World' all leaders after c.650AD were Muslims) affiliating yourself with a wider culture that provided trained intellectuals who could connected themselves to a much wider world than was the case under 'Paganism', which was usually a very localist form of religious expression. Again, social networks.
I think that's a major part of the explanation though it is rather Eurocentric and ignores cases like the disappearance of Hinduism from South East Asia except in weird outliers like Bali or the spread of Christianity in Africa since the 19th Century (although then again, perhaps not, but I'm not read enough to judge). Most of all, there is the still case of how 'Hinduism' survived in India or how religion was never formalized in China or Japan (until 1868, but even then...). However even in those cases I would say states were important, they clearly were in the Islamic conversion of parts of South Asia but no state in India, except briefly Aurangzeb and he failed, ever tried to impose religious conformity over the whole landmass, the place was nearly always too politically fractured for that anyway (although this might not stop the BJP from trying in the future). In China and Japan state Confucianism ebbed and flowed between tolerance and hostility towards religious doctrine, but never did it managed to replace state Confucianism, which took up many of the roles that Christianity and Islam did in their particular spheres (or at least in China in which I know more of, Madeleine can fill in the details wrt Japan).
