What is the earliest historical instance of state-paid Clergy?
Perhaps not exactly paid clergy, but the State began indirectly to help the clergy in the time of Constantine. It is not quite the same thing.
In Constantine’s day the clergy were aided in a number of ways with substances for living, but did not receive outright wages from the State! They did receive some monetary help, but not wages properly speaking.
In fact, even up to the sixth century, the clergy worked to support themselves.
Direct support of the clergy by the State is of comparatively modern origin, having developed since the Reformation.
It is all in the following article from the Catholic Encyclopedia:
A stipend is a fixed pay, salary; retribution for work done; the income of an ecclesiastical living. In canon law stipend is a general designation of means of support (sustentatio congrua or congrua) provided for the clergy. In the early ages of the Church no special provision was made for the maintenance of the clergy. St. Paul, the tent-maker, set the example (1 Corinthians 4:12) of earning his own livelihood. In imitation of him many clerics worked at some craft or followed some profession, living by the labour of their own hands. Even in the fifth and sixth centuries there were bishops, priests, and deacons, who in keeping with the advice of the Fourth Council of Carthage (a. 398, cann. 52, 53) supported themselves by their own labour. Early legislation (Canon. Apost., can. 6), which forbade the clergy to take up certain occupations and professions, is an indication that clerics sought to maintain themselves. Many of the laity, however, even from the beginning, were quick to follow the instructions of Christ and his Apostles (Matthew 10:10; Luke 10:7; 1 Corinthians 9:13; 1 Timothy 5:17-18), founded on the practice in vogue among the Jews (Leviticus 27:30 sq.; Numbers 18:23 sq.; etc.), who gave tithes of all their goods and produce for the sustenance of priests and levites. Thus did the laity provide for the bodily welfare of the clergy in return for the spiritual gifts received through their ministry. Later the payment of tithes was frequently insisted on by St. Ambrose, St. Augustine, and others (Thomassin, "Vet. et nov. eccl. disc., " III, II, xii, xiv). The Synods of Tours (560) and Mâcon (586) strenuously exhorted the faithful to pay the tithes ordained by God. Charlemagne made their payment obligatory on his subjects by a royal ordinance of 779, the requirements of which he himself faithfully observed. The obligation of giving tithes has long since ceased almost universally, but the faithful, of course, must contribute to the proper support of sacred ministers.
In regard to so-called state aid of the clergy, the State began indirectly to help the clergy in the time of Constantine, who gave a legal existence to churches as corporate bodies, permitting them to receive donations and legacies and to hold the same in perpetuity (Cod. Theod., XVI, 2, 4). He ordered contributions of grain to be given annually to the clergy out of the public granaries. He contributed large sums from his own resources for the support of the clergy in Africa, and exempted the Church from imposts in an edict imposing a general tax (Cod. Theod., XI, i, 1). Direct support of the clergy by the State is of comparatively modern origin, having developed since the Reformation. It obtains particularly in Catholic countries that have entered into a concordat, or treaty, with the Holy See for the support of the clergy. This support is in recompense, far inadequate indeed, for the sequestration of ecclesiastical funds and property. Austria, Spain, Italy, and certain countries of Central and South America thus directly support the clergy, paying salaries to bishops, vicars-general, pastors, and assistants. France and Portugal, as well as Cuba, Porto Rico, and the Philippines, when under Spanish rule, did the same.
Since the time of Constantine the right of the Church to possess temporal goods has been universally acknowledged and protected by civil governments with some exceptions. These exceptions refer chiefly to bequests and legacies. The possession by the Church of temporal goods and the surrendering of the same to the clergy for their sustenance gave rise to benefices, the fruits or income of which constitute the chief provision for the maintenance of the clergy possessing them. The fruits of a benefice will maintain the incumbent, even though he have private means of support. He should have not only what is necessary for sustenance, but sufficient for fitting recreation and hospitality, and a modest portion for future contingencies: he may also assist near relatives to some extent. If anything remain, it is to be used in charitable works. Ecclesiastical goods are not to be bequeathed in any considerable quantity to profane purposes. There are other methods in vogue for the support of the clergy akin to, or divisions of, those mentioned: voluntary offerings, tithes, quasi-contracts, state aid, and benefices. Stipends for the application of Masses were originally intended for the daily maintenance of the celebrant. - Stipend (Catholic Encyclopaedia)
Wikipedia states that as far as Constantine was concerned the Jewish clergy were given the same exemptions as Christian clergy.
We also see that in the late fifth and early sixth centuries that Queen Shirin supported the Church in Iran, but the political situation demanded that she do so discreetly. Once again, source do not indicate a state wide wage for the clergy. Queen Shirin seems to support in the second paragraph Clergy that were to some degree attached to the royal court.
Shirin (? – 628 AD) (Persian: شیرین) was a wife of Khosrow Parviz. In the revolution after the death of Khosrow's father Hormizd IV, the General Bahram Chobin took power over the Persian empire. Shirin fled with Khosrow to Syria, where they lived under the protection of Byzantine emperor Maurice. In 591, Khosrow returned to Persia to take control of the empire and Shirin was made queen. She used her new influence to support the Christian minority in Iran, but the political situation demanded that she do so discreetly. Initially she belonged to the Church of the East, the so-called Nestorians, but later she joined the miaphysite church of Antioch, now known as the Syriac Orthodox Church. After conquering Jerusalem in 614, amidst the Byzantine–Sasanian War of 602–628, the Persians captured the True Cross of Jesus and brought it to their capital Ctesiphon, where Shirin took the cross in her palace.
The Roman (Byzantine) ancestry of Shirin is contradicted by Sebeos: "[Xosrov], in accordance with their Magian religion, had numerous wives. He also took Christian wives, and had an extremely beautiful Christian wife from the land of Xuzhastan named Shirin, the Bambish, queen of queens. She constructed a monastery and a church close to the royal abode, and settled priests and deacons there allotting from the court stipends and money for clothing. She lavished gold and silver [on the monastery].
The very first concordat with the Holy See was with Ecuador in 1862. As seen here, it made provisions to support it’s Catholic clergy.
As the proceeds of the tithes are destined for the upkeep of Divine worship and of its ministers, the Government of Ecuador binds itself to preserve this Catholic institution in the Republic and His Holiness consents that the Government should continue to receive a third part of the proceeds of tithes. The two authorities (civil and ecclesiastical) shall come to an agreement about the collection and administration of tithes.
The Holy See, in exercise of its particular prerogative, shall create new dioceses and shall make new delimitations in those at present existing; and taking into account the present extent of the dioceses among which the Republic is at present divided, the Holy See will, immediately on ratification of the present Concordat, confer on its own special delegate the necessary powers to proceed in consultation with the Government and the respective bishops to the territorial demarcation of the dioceses which can be conveniently created and to fix the endowments and salaries of churches, bishops, chapters and seminaries.