When was the idea of a well-formed formula first stated or can get inferred as such under another name?
That's an interesting historical question. The answer, I think, must be "a bit later than you might imagine". The idea isn't in Frege. Frege's Begriffsschrift is apparatus added to mathematical German for the purpose of rigorously expressing logical relations; he didn't think of it as a stand-alone formal language with a closed set of syntactic rules in the modern sense. It certainly isn't in the famously careless Principia.
The idea of a (well-formed) formula is, however, explicitly there in Hilbert and Ackermann's Grundzüge der Theoretischen Logik of 1928. You will find the now familiar kind of recursive definition for the wffs of a predicate calculus at p. 66 of the English translation. I wouldn't at all be surprised to learn that Hilbert in his lectures earlier in the 1920s gave the first really clear statement.
It is difficult to exaggerate the historical significance of Hilbert and Ackermann's book (and hence of Hilbert's earlier lectures on which it is based). The first recognisably 'modern' logic book, it is still very worth reading.