This is a great and really complicated question, and one that unfortunately in a lot of ways I don't think can be comprehensively answered but I hope I can try to untangle some of these terms and point you towards some further reading that might be useful.

I also just want to point out that I'll be writing about this from from a secular perspective, so while I haven't read Tahirul Qadri, I suspect he and I will be approaching some of these questions based on very different assumptions about, say, early Islamic history, just to give an example.

On early Islamic history, I'll call this:

Part I

As far as I know their was no such concept of state religion in the charter of medina.

Historians are generally of the consensus that before Muhammad, there was no such thing as a "state" in Arabia.

Your point here also raises questions about what Muhammad was doing in Medina, how it related to the creation of a "state," and how that state related to a religion of "Islam."

First, what our historical sources? I've written a lot here in the past about why early Islamic history is so difficult to interpret because of our lack of sources, for example here.

Effectively, from a secular perspective our only sources here are the Qur'an and the charter/constitution of Medina. And even for the Qur'an, so much of what we "know" about its text is actually the interpretation from tafsir. Again I would point you that previous post I wrote, but from a secular historical perspective, the tafsir effectively have to be thrown out, leaving us with an incredibly vague Qur'an that is very difficult to interpret.

One of the critical elements of examining the Qur'an is the attempt to date when its passages were revealed to Muhammad. The standard, contemporary dating of these revelations and their arrangement is actually surprisingly recent: again, cutting a very long story short, the standard agreed upon version among Muslim believers is the 1924 Cairo edition.

Believers would of course reject the idea that there is any change in the meaning or purpose in the Qur'an over the course of its revelation: it is the word of God.

Secular analysts, however, might draw very different conclusions. Crucially, both believers and secular scholars divide the Qur'an into Meccan and Medinan suras. The Meccan suras are those that were revealed to Muhammad early in his life before the hijra while he was still in Mecca, while the Medinan suras are those revealed after the hijra when he had effectively assumed the power of a head of state.

In qualitative terms, the Meccan suras tend to be shorter, more poetic, and more mystical. By contrast, the Medinan suras, when Muhammad had acquired a leadership position over a proto-state, are much longer, and have the character of law giving. The sura al-Baqarah is the longest sura of the Qur'an and was the first revealed to him in Medina. Because the Qur'an is effectively organized by length, it is also the first verse of the Qur'an after the very short opening sura al-Fatiha.

From a secular perspective, al-Baqara does a lot for a community that would have been relatively new to Muhammad's message.

It says what the Qur'an is:

This is the Scripture whereof there is no doubt, a guidance unto those who ward off (evil).

It says what the community of believers is and why they should believe:

And who believe in that which is revealed unto thee (Muhammad) and that which was revealed before thee, and are certain of the Hereafter.

These depend on guidance from their Lord. These are the successful.

It says who the disbelievers are and what will happen to them:

As for the Disbelievers, Whether thou warn them or thou warn them not it is all one for them; they believe not.

Allah hath sealed their hearing and their hearts, and on their eyes there is a covering. Theirs will be an awful doom.

These are all of course sequential verses at the very opening of the first verse revealed to Muhammad in Medina.

At a basic level, to your question about a state religion:

Surely this is the introduction to a political community of what the religion of their state is to be?

This Sura itself goes on (at great length) to try to convert the people, to warn of what happens to those that don't convert, to lay down new law, etc. etc.

Much of the religious Muslim analysis of this sura and of the early history of Islam distinguish, even at this early period, between "Muslims" as a distinct religious group that was distinct from Christians and Jews.

This, however, from a secular perspective, raises the question: What was Islam in the period?

Our lack of early sources, and the evidence from the early documentary sources that we do have has led some scholars to reach radically different conclusions from the traditional Islamic narrative.

Fred Donner's Muhammad and the Believers, for example, and to summarize a subtle and sophisticated book-length argument, argues persuasively that what Muhammad had assembled was not Jews, Christians, and "Muslims", but a community of believers, effectively all Muslims, but of which "Muslims" came to denote those who simply had not been prior Christians or Jews, and rather had been (in the Islamic tradition) sometimes described as "hanifs" or Arab pagan converts.

Again, what this latter category of "muslims" actually was is confusing and not entirely clear. For one thing, it seems clear in the earliest periods that it was inextricably linked to being Arab. It was not originally possible to convert to Islam without becoming a mawlid, an Arab tribal client. Effectively, converting to Islam also meant converting to being an Arab.

This is relevant in the context of what the early conquest state was. Should we call them the "Islamic" conquests or the "Arab" conquests. The general historical consensus today is that "Arab" is the stronger argument, in part because especially in the west, the Arabs Muslims were conquering fellow "believers" and seem to have, for example, shared religious spaces with Christians.

The governance of this early empire is another area where the religious Islamic narrative clashes with and confuses the question of when the Arab empire became one with a state religion.

Critically, for example, Q9:29 reads:

Fight against such of those who have been given the Scripture as believe not in Allah nor the Last Day, and forbid not that which Allah hath forbidden by His messenger, and follow not the Religion of Truth, until they pay the tribute readily, being brought low.

This is Pickthall's translation, and the word "tribute" here that he is translating in Arabic is "jizya" a word that is often left untranslated by other translators because it later became understood to mean the poll tax that Muslims applied on non-Muslims, e.g. that Mamluks applied on Christians and Jews in Medieval Egypt. I.e. it our later narrative understands it as an explicitly religiously discriminatory tax.

But Pickthall's translation is actually correct. In context, it seems that the early Muslims simply understood "jizya" to mean a kind of tributary tax that could be collected by any ruling party on their subjects, not some special innovation of the Muslims to be collected from non-Muslims (which, again, are categories that they would not have understood as we understand them anyways.)

This is discussed by both Donner and in Robert Hoyland's In the Shadow of the Sword.

---

I think you can start to see some of the elements that I'm trying to untangle from your original question:

• State
• Religion
• Muslim

These are all terms that in the context of Muhammad and early Islamic history are very difficult to pin down, but most generously defined we might say something like:

Muhammad in Medina created a state (minimally defined) that was based on religion in terms of its scope (i.e. who was part of the state and who was not) and its laws (revealed by God) that consisted of believers (i.e. Muslims, maximally defined).

In that sense, I think the answer to your question is that a state religion comes into Muslim political consciousness effectively from the very beginning.

Shadi Hamid in his book Islamic Exceptionalism I think examines a lot of these questions in an interesting way, looking at how the Islam is fundamentally related to the formation and creation of a state in a way that differentiates it from other religions (except as many, many other scholars have noted, with Judaism, which Islam resembles in many ways far more closely than with Christianity.)

---

But again, I don't think this is really what you're getting at, because a big part of what this leaves out is how we even get to the classical Islamic religious distinctions between, for example, Muslim, Christian, and Jew, and how an Arab empire became "Islamic" and had a "state religion" of the kind that I think that you're driving at, by which I think you mean something closer to what might be termed an imperial religion.

For that we have to look at:

Part II: The Late Antique and Early Medieval Context

Islam emerged in the periphery of the two great empires of the 6/7th century Middle East. The Christian Byzantine [Roman] Empire, and the Zoroastrian Sassanian [Persian] Empire.

This part, I think, will be the shortest of the ones I write because it's the part I'm least qualified to write, but in the battles between these two empires you increasingly have two systems that, so far as we can tell in their coinage and other evidence of their propaganda, are defining their conflicts between each other and the the legitimacy of their own systems, in terms of religion.

[Running out of characters, will continue in a second post]

edits: A number of typos.