'Set foot' as an idiomatic antecedent to 'step foot'
The expression "set foot" goes back to circa 1600, according to Christine Ammer, The American Heritage Dictionary of Idioms, second edition (2013), and has two major forms: "set foot in" and "set foot on":
set foot 1. set foot in. Enter, as in I'll never set foot in the house again. 2. set foot on. Step on on, as in We were so happy to set foot on dry land. {c. 1600}
A search of Early English Books Online turns up a match for "set foote in" from James Harrison, An Exhortacion to the Scottes to Conforme Them Selfes to the Honorable, Expedie[n]t, and Godly Vnion, Betwene the Twoo Realmes of Englande and Scotlande (1547):
These Pictes wer a people of Scithia, now called Tartarie, & driuen out of their countrey, sought herberough emonges Irish Scottes, who beyng nothing glad of such gestes, procured theim to set foote in Brytayne as thei did in deede, and ther continued many yers after.
And it finds an instance of "set foot on" from André Thevet, The New Found Worlde, or Antarctike (1568):
The sayd people [of "this Countrey of Ginney"] haue neither temples nor churches, nor other places appoynted for sacrifice and prayer. Besides this, they are without comparison much more wicked than those of Barbarie or Affrica, in such sort that the straungers dare not aborde them, nor set foote on land, but by pledges: otherwise they would take them, and handle them like slaues.
Overall, EEBO finds 288 matches for various forms of "set foote" and 788 matches for various forms of "set foot"; some of these matches are accidental juxtapositions of the two words, rather than instances of the idiomatic phrase, and some are duplicates—but hundreds are relevant unique instances of the idiomatic phrase.
In contrast EEBO returns no relevant matches for various forms of "step foote" or "step foot." It follows that instances of "step foot" are almost certainly variants of the earlier "set foot."
'Step foot in' in nineteenth century U.S. newspapers
Although "set foot in" in much older and vastly more common than "step foot in," instances of "step foot in" go back more than 150 years in U.S. newspapers. From an untitled item in the [Evansville, Indiana] Daily Journal (October 30, 1855):
It is said Gov. Wright's lady has presented him with two bouncing boys. The Governor need not think he is doing his party any good by this. They cannot have the privilege of casting a vote till they are twenty-one years old—but foreigners, the majority of whom don't know any more about our institutions than these infants, in six months after they step foot in this country, can vote in Indiana. In twenty-one years the Governor's party will be dead and forgotten.
From "Letter from Marshall," in the [Houston, Texas] Weekly Telegraph (January 1, 1861):
I wonder if his Excellency [Governor Sam Houston] saw the second provision of that act, which authorized him to call the Legislature together, upon the same contingency; perhaps his ADVISORS, Cave and Norton, didn't show it to him. These two grand viziers of his R. H., I notice, are against the "traitorous" actors in this secession move. If they were to dare to step foot in this county, advocating their Lincoln foot-licking, they would meet the penalty which overtakes Tories and traitors to their country.
And from "News of the Week," in the [M'connelsville, Ohio] Conservative (November 30, 1866):
A New York dispatch says James Stephens has disappeared, and gone on a secret mission. He left his office in that city a few days ago in company with four men who had arrived from Ireland, and were armed with a new kind of revolvers, specially manufactured for them. Stephens took leave of his friends, saying he should never again step foot in his office.
Altogether, an Elephind database search of historical U.S. newspapers for "step foot in" returns 21 unique matches from the second half of the nineteenth century and dozens more from the twentieth century.
'Step foot in/upon' in early nineteenth-century sources
Google Books searches yield a number of matches for "step/steps/stepped/stepping foot in/on/upon/within" from decades before the earliest Elephind matches. Multiple Google Books matches come from the first half of the nineteenth century—from both U.S. and British sources. The earliest of these is from "Cockolorum Sentiments, &c." in The Cockolorum Songster, and Convivial Companion for 1800 (London, 1800):
In our journey through life, may we never step foot in the road to ruin.
Other very early instances include the following three.
From "An Address to the Inhabitants of the Counties of Greene and Delaware, and Their Vicinities," in The Columbia Magazine (Hudson, New York: March 1815):
Intemperance, in its lowest grade, is an evil, and ought to be shunned as the almost certain precursor to inevitable destruction. It almost for ever casts down those who step foot upon its enchanted ground. Its grasp is death. It is easy falling ; many go down into the pit, but not one of a thousand returns.
From The Revealer of Secrets; Or, the House that Jack Built (London, 1817):
The servants who were left, full of revelry and riot, were packing up, and tumbling about the luggage, with no more concern for Hammond than if he had not been in the house, all eager to get away from what they declared to be the most dead-alive place they ever saw, and the meanest, most disagreeablest house that they ever stepped foot into.
And from "Excursion from Edinburgh to Dublin," in The Analectic Magazine (Philadelphia, Pennsylvania: December 1819):
The British coast is gradually receding, and the Irish slowly enlarging on the view. I left the former with some emotion—impatient to step foot upon the 'land of sweet Erin' ; a country where I expect to find much that is new to amuse and instruct me.
I note that a later chapter of this serialized travelogue, which appears in the June 2020 issue of The Analectic Magazine, contains the instance of "stepping foot again upon" cited in user 66974's answer (which relies on the dating that appears in Wictionary's entry for "step foot"):
At three P. M. we dropt anchor in the little part of Whitehaven, and the next minute found me once more upon English ground. This was a pleasure of no small kind ; and in stepping foot again upon the soil of that country, which contains much that I prize, and more that I admire, I could not refrain from repeating to myself,—"England, with all thy faults, I love thee still."—
Wictionary's dating of that quotation to 1813, however, appears to be erroneous. In the first installment of the "Excursion" series, in The Analectic Magazine (October 1819), the author reports that the trip took place in "the Spring of 1817"; and whether the wording was composed at that time or later, The Analectic Magazine didn't publish it until 1819–1820.
Conclusion
The upshot of the evidence from searches of the Elephind and Google Books databases is that, whether you view "step foot in" as a legitimate variant of "set foot in" or an illegitimate error, the expression is by no means a recent coinage. It has appeared in published works since at least 1800, and I suspect that people have been saying it for longer than that.