When did the idea of macros (user-defined code transformation) appear?

I think the idea goes back to Post systems, rewriting with strings ("if you see this string, replace it with that string"). Post systems are Turing-capable, and can thus compute anything (including program texts!). Emil Post's paper on these is dated 1943, but supposedly he did the original conceptualization in the 1920s.

The General Purpose Macro Processor, one of the first widely used ones, was available in the early 60s.

TRAC is another early macro processor dating to the same period. The History of Computer Languages (TRAC) says it was designed in 1959.

Both of these are Turing-capable macro processors.

SNOBOL also dates from the same period.

The fact that very general-purpose macro processors were being built in the early 60s hints to me that there were likely special-purpose macro processors built before then to provide inspiration. I'm pretty sure macro processors were in use in assemblers before this point, but I don't have specific evidence.

I know that COBOL has so-called COPY libs, which are a cross between macros and include files. I don't know when this was introduced into COBOL, but the langauge goes back to 1958.

It is interest to note that LISP macros can be considered to be a special case of tree-to-tree rewrites ("if you see an s-expression that looks like this, replace it by an s-expression that looks like that"). Trees can be easily modelled as strings (see: "LISP" :) and thus LISP macros are a special case of string rewriting.

The generalized case of tree-rewriting is now the basis for Program Transformation Systems, which can carry out massive changes on program text.

To look for how macros where introduced into Lisp, you should look for mentions of FEXPRs and FSUBRs which the predecessors of modern Lisp macros (or more accurately, FEXPRs are the predecessors of user-defined macros). These are mentioned in several places -- for example, in the From LISP 1 to LISP 1.5 section of McCarthy's History of Lisp. But in fact, it's also mentioned earlier than that: in p.48 of the LISP I PROGRAMMER'S MANUAL (from 1960) you can see a description of FEXPRs and FSUBRs.

BTW, it's a little bogus to compare Lisp macros with string-based systems. The advantage of using a tree transformer vs string manipulations is significant enough to make it a completely different system. Another important aspect of Lisp macros is that they are local transformation vs a global program transformation (the most obvious paper to read for this is Felleisen's On the Expressive Power of Programming Languages). And of course there's a whole area here -- going from FEXPRs to the modern, more well behaved macros, then to hygienic macros in Scheme (which deal with a representation that is richer than symbolic parse trees), then a combination of macros and a module system, syntax expansion phases, etc etc etc. There's probably enough stuff here for a few years of reading...