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$.
No, it’s not always upwards-directed.
The underlying set will be $\mathbb Q.$ Define relations $<_n$ by
$$a<_n b \iff n<a<b<n+2.$$
Take $\mathfrak A$ to have relations $<_n$ for $n$ even, and take $\mathfrak B$ to have relations $<_n$ for $n$ odd. These models have the same definable sets. $\operatorname{Aut}(\mathfrak A)$ is the group of order-preserving bijections fixing the even integers. $\operatorname{Aut}(\mathfrak B)$ is the group of order-preserving bijections fixing the odd integers.
By a shuffle that does not translate well to text (though I can try if you like!), the map $\tau:x\mapsto x+1$ is a composition of bijections in $\operatorname{Aut}(\mathfrak A)\cup \operatorname{Aut}(\mathfrak B).$ Consider a unary relation $U(x)$ that is definable by a formula $\phi(x,y)$ in $\mathfrak A$ with a tuple $y$ as a parameter. For sufficiently large integers $N,$ the parameter $y$ and all operations and relations used by $\phi$ are invariant under bijections that fix $[-N,N].$ If $U$ is invariant under $\tau^{4N},$ then it must also be invariant under bijections that fix $[3N,5N].$ This can’t happen unless $U$ is either $\emptyset$ or $\mathbb Q.$
In particular $U$ cannot be the interval $(0,2)=\{x:x<_0 2\}.$ So no $\mathfrak C\approx \mathfrak A$ can be $\tau$-invariant.
Best Answer
No to the title question, yes to the question in the post.$\DeclareMathOperator{Aut}{Aut}$ Pick an infinite set $X.$ Pick infinite coinfinite sets $Y_A,Y_B\subseteq X$ with $Y_B=Y_A\cup\{y\}$ for some $y\not\in Y_A.$ Define $\mathfrak A$ and $\mathfrak B$ to have
These have the same definable sets.
Suppose for contradiction that there is a structure $\mathfrak C$ with $\mathfrak C\approx\mathfrak A$ and $\Aut(\mathfrak A)\cup\Aut(\mathfrak B)\subseteq \Aut(\mathfrak C).$
$\Aut(\mathfrak A)$ is the group of symmetries fixing $Y_A$ setwise, and $\Aut(\mathfrak B)$ is the group of symmetries fixing $Y_B$ setwise.
$\Aut(\mathfrak C)$ contains every transposition $\pi$ swapping an element $x\in Y_A$ with an element $x'\in X\setminus Y_A.$ I will try to actually describe the symmetry this time. Recall $y\in Y_B\setminus Y_A.$ Conjugate $\pi$ by a transposition in $\Aut(\mathfrak A)$ to reduce to the case $x'=y.$ Then use a transposition in $\Aut(\mathfrak B)$ to swap $x$ and $x'.$ (More generally, $\Aut(\mathfrak C)$ contains all permutations $\pi$ of $X$ such that $|\pi(Y_A)\setminus Y_A|$ and $|Y_A\setminus \pi(Y_A)|$ are finite and of equal cardinality.)
By the assumption $\mathfrak C\approx\mathfrak A$ there is a sequence of parameters $y_1,\dots,y_k\in X$ and a relation symbol $R$ such that
$$z\in Y_A\iff R^{\mathfrak C}(z,y_1,\dots,y_k).$$
Let $Y_0=\{y_1,\dots, y_k\}.$ Pick $x\in Y_A\setminus Y_0$ and $x'\in X\setminus (Y_A\cup Y_0).$ We must have $R^{\mathfrak C}(x,y_1,\dots,y_k)$ and $\neg R^{\mathfrak C}(x',y_1,\dots,y_k).$ But there is a symmetry of $\Aut(\mathfrak C)$ swapping $x$ and $x’$ and fixing all elements of $Y_0.$ This contradicts the choice of $\mathfrak C.$