There are only two general conditions (that I know of) under which automorphism-invariant implies definable (in first-order logic): (1) the trivial case when $\mathfrak{M}$ is finite, and (2) when $A$ is finite and $\mathfrak{M}$ is the unique countable model of an $\aleph_0$-categorical theory. In this case, the result is a consequence of the Ryll-Nardzewski theorem.
Why are such strong hypotheses necessary? Just for easy cardinality reasons!
For simplicity, let's assume our language $L$ is countable. Now suppose $A\subseteq M$ is an infinite set. Then any subset $B\subseteq A$ is invariant under automorphisms fixing $A$. And there are $2^{|A|}$ subsets of $A$, but there are only $\text{max}(|A|,\aleph_0)$ $L$-formulas with parameters from $A$. So there just aren't enough formulas to define all the invariant subsets, even of $A$.
Ok, so we have to restrict to finite sets of parameters. To make it even simpler, let's take $A = \emptyset$. Now the action of $\text{Aut}(\mathfrak{M})$ partitions $M$ into orbits, and a set $S\subseteq M$ is invariant under the action of $\text{Aut}(\mathfrak{M})$ if and only if it is a union of orbits. To put it another way, if $\mathcal{O}$ is the set of orbits, then an invariant set has the form $\bigcup_{O\in X} O$ for some set of orbits $X\subseteq \mathcal{O}$. Now again, if $\mathcal{O}$ is infinite, then there are $2^{|\mathcal{O}|}$ invariant sets, but only countably many formulas, so there must be invariant sets that aren't definable.
So we can only hope to get definability of every invariant set if the action of $\text{Aut}(\mathfrak{M})$ on $M$ has only finitely many orbits. If you want invariance to imply definability not just for subsets of $M$ but also for subsets of $M^k$ for all $k$, then you need to assume that the action of $\text{Aut}(\mathfrak{M})$ on $M^k$ has only finitely many orbits for all $k$ - and this is exactly the definition of an oligomorphic group action. By the Ryll-Nardzewski theorem, if $\mathfrak{M}$ is countably infinite and the action of $\text{Aut}(\mathfrak{M})$ is oligomorphic, then $\mathfrak{M}$ is the unique countable model of an $\aleph_0$-categorical theory.
There are other more exotic situations when every invariant subset of a model is definable: for example, the language could include a relation symbol for every subset of $M^k$ for every $k$ (note that in this case, the cardinality of the language is larger than the cardinality of $M$). As far as I know, there is no general theory of these sorts of examples.
See also the question and answers here. In particular, the note at the bottom of my answer might be of interest to you: if we're willing to work with the infinitary logic $\mathcal{L}_{\omega_1,\omega}$, then Scott's isomorphism theorem tells us that every invariant subset of a countable structure is definable by a formula of $\mathcal{L}_{\omega_1,\omega}$. But this does not apply to structures of higher cardinality in general, even if we look at infinitary logics of the form $\mathcal{L}_{\kappa,\lambda}$ for other cardinals $\kappa$ and $\lambda$.
Best Answer
As Eric Wofsey said, actually building an automorphism of $\mathbb{C}$ which moves a real is difficult: while we can prove that for every transcendental real $r$ there is a field automorphism of $\mathbb{C}$ which moves $r$, this proof is $(i)$ a transfinite recursion argument and $(ii)$ relies on the axiom of choice.
There is, however, an automorphism argument which does work:
We'll show a stronger result - that for any transcendental real number $r$ and any formula $\varphi(x)$ such that $\mathbb{C}\models\varphi(r)$, there is a non-real complex number $s$ such that $\mathbb{C}\models\varphi(s)$. The argument uses automorphisms and elementary submodels, and goes as follows (outlined only - it's a good exercise to fill it all in):
Fix a transcendental real $r$, a transcendental non-real complex number $s$, and a formula $\varphi(x)$ such that $\mathbb{C}\models\varphi(r)$. Let $M$ be a countable elementary submodel of $\mathbb{C}$ which contains $r$ and $s$ - we know such an $M$ exists by the downward Lowenheim-Skolem theorem.
Now show that $M$ is a countable algebraically closed field of characteristic zero and infinite transcendence degree.
By a standard back-and-forth argument, there is an automorphism of $M$ swapping $r$ and $s$, so $M\models\varphi(s)$. Back-and-forth arguments are still recursive constructions, but they don't use transfinite recursion; also, this is probably a result you've already proved.
Remembering how $M$ and $\mathbb{C}$ are related, conclude that $\mathbb{C}\models\varphi(s)$ as desired.
Remark $1$. We can avoid elementary submodels entirely by working with Ehrenfeucht-Fraisse games instead; however, elementary submodel juggling is an important technique to learn.
Remark $2$. An even stronger fact is true: $\mathbb{C}$ is strongly minimal, meaning that for any model $N$ of $Th(\mathbb{C})$, every definable-with-parameters subset of $N$ is either finite or cofinite. (First, prove that $\mathbb{C}$ has quantifier elimination, and then show that every quantifier-free formula with parameters defines either a finite or a cofinite set; then lift this to every model of $Th(\mathbb{C})$.)