Sometimes the next step in a research question is to find a new primary source. But not this time.
Volker Leppin's Antichrist und Jüngster Tag has an extensive section (pp. 144-49) on the 1588 quatrain which identifies the first source in print as Kaspar Brusch's preface and afterword to the 1553 edition of the De ortu et fine Romani Imperii liber of Engelbertus von Admont (VD16 E 1211). The BSB has digitized this edition, and the page with the quatrain is here, while the Latin verse is here. This appears to be the first recorded appearance of the prophecy in print.
The note on the title page is interesting, however: Accessit eiusdem Bruschij Hodoeporicon Bauaricum, in quo et Regiomontani uaticinium quoddam explicatur, et uaria de die extremo conijciuntur, "Also including Brusch's Bavarian Travels, in which a certain prophecy of Regiomontanus is explicated and various things concerning the Last Day are conjectured." The quatrain appears to have been associated with Regiomontanus and well known enough in 1553 that it merited mention on the title page.
There are similar and competing quatrains for earlier years (and eventually for 1590 and later), and Latin verse for 1560, so we wouldn't expect the 1588 quatrain to get started much earlier than this, but there may yet be earlier witnesses to be found. I'm still curious why someone in 1553 or earlier was focused on the year 1588.
Volker Leppin's book is excellent, by the way. I'm adding it to what has been a very short list of books that are fundamental foundational reading for prophecy and prognostication in early modern Germany.