It appears that:
- This language was seen as a bit ridiculous and unnecessary even at the time, and more so as the 19th century progressed.
- The main objection is that the language is redundant or merely decorative. There was a general trend to make indictments describe the alleged offences in more ordinary language, with use of precise legal terms when needed. In particular, indictments were made to match the legal elements of the offence that were required to be proved, rather than being polemics about the wickedness of the offender.
- Different jurisdictions abandoned it at different rates, depending on local circumstances. There does not appear to be any particular campaign about it, and since the language was seen as unnecessary rather than wrong, some prosecutors continued to use it without problems.
- Religious freedom, or establishment of religion, has nothing do to with it. Much of the common-law understanding was driven from England where the constitutional settlement was completely different. Despite the mention of God and the Devil, this was a completely stock phrase that was devoid of any real religious content.
My main sources here are 19th century legal textbooks, which contained some citations to case law. There does not seem to have been very much statutory activity.
Quoting from Joel Prentiss Bishop's New criminal procedure; or, New commentaries on the law of pleading and evidence and the practice in criminal cases (Chicago: T. H. Flood, 4th ed., 1895), section 501 in volume 1:
It was formerly the style, nor at the present day is it quite abolished, to charge, especially in treason and felony, that the defendant did it "not having the fear of God before his eyes, but being moved and seduced by the instigation of the devil." Both in reason and by all authority, these words are not necessary. Their original purpose seems to have been to make the accusation correspond in form to the fact; for, as Cotton Mather said, speaking of what he and others of this time believed: "When men do commit a crime for which they are to be indicted, they are usually moved by the instigation of the devil." Yet even in this view, they could never have been required; because in law, no "instigation" to crime justifies the doer, so that the devil's instigation is wholly immaterial.
Among other sources he cites Joseph Chitty's A practical treatise on the criminal law, which in an early American edition (Philadelphia: Isaac Riley, 1819) confirms at 240 that these words concerning the Devil "though usual, are not necessary to be inserted", elaborating that
where the common law, or a statute, forbids the doing of a thing, the doing it wilfully is indictable, though without any corrupt motive, and consequently it need not in any case be averred.
There are several other textbooks that discuss related but less colorful terms, such as "wilfully" or "wickedly", using essentially the same argument for why they are unnecessary. The idea is that when somebody is being tried for murder, the prosecutor is trying to show that they killed someone on purpose - not that they were wicked while doing it, which is implicit, or that the Devil was metaphysically responsible, which is irrelevant.
Many of these books seem to copy the language from Joseph Burn's Justice of the Peace and Parish Officer at section 11 of the entry on "Indictment" (references omitted) in volume 3 (London: 26th ed., 1831):
The words "wickedly, maliciously, of his own wicked and corrupt mind, being a person of evil disposition, &c." are, in general, mere matter of aggravation and not material. But where an act must be done with a particular intent, in order to render it criminal, an evil intention must be averred upon the record; and, in such case, the intent must be proved as laid or the variance will be fatal.
From the general tenor of these books, we can see that there were great difficulties with indictments that did not match the legal requirements of the offences to be tried: there are several accounts of defendants who were able to defeat the charges because of drafting problems. Additionally, the idea of a right to a fair trial (whether seen as a matter of natural justice, or founded in positive law such as the Sixth Amendment right "to be informed of the nature and cause of the accusation") added pressure on prosecutors to express the charges with precision and clarity. The textbooks are overall quite scathing about the inclusion of decorative phrases.
In case law, an American case that is directly on point is from Massachusetts, Commonwealth v Murphy 11 Cush. 472 (1853), which apparently confirms the devil-reference as unnecessary, though I haven't located the primary source. For the general idea of these references being not essential, the textbooks mainly cite an English case from the Court of King's Bench, R v Philipps (1805) 6 East 472. The Lord Chief Justice, Lord Ellenborough, considered an indictment alleging among other things that Philipps "wickedly and maliciously did endeavour to stir up, provoke, and excite [someone else] to challenge the defendant to fight a duel with him". Citing Lord Mansfield in the seditious libel case of R v Woodfall (1770) 5 Burr 2667, he said that terms of opprobrium like "wickedly" were "mere formal inferences of law" and did not contribute anything material to the description of the offence and any required element of intent. The defendant's counsel in Woodfall had objected to what the judge described as "the usual epithets", and the judge told the jury to ignore them but concentrate on the alleged facts: they were not being asked to determine whether the publication was sufficiently odious to deserve the colourful language used in the indictment. By extension, juries are not asked to make determinations about the theological circumstances surrounding sinful acts and the agency of the devil.
The 1805 case, coincidentally about duelling, is from after the Burr-Hamilton duel and it evidently took a while for this logic to penetrate the legal community in general (Bishop in 1895 calling the devil phrase "[not] quite abolished"). Notably, while the case does not rest on any specifics of the American legal or cultural order, it does appear to have been influential on American jurists who accepted it as a statement of the common-law position. The American writers do not raise any objections to the phrase on grounds relating to religion, and universally treat it as "stock" language.