So even though the question talks about the language of set theory specifically, let me answer the question more generally.
Also, I'll talk about definable subsets of $M$, as opposed to definable sbsets of the Cartesian powers of $M$ - for example, we can ask "When is a set of ordered pairs of elements of $M$ definable?" The answer is a straightforward generalization of what I write below, and coming up with it is a good exercise.
Let me first describe definability without parameters. That is, what I talk about below will be not taking into account the $a_i$s of your question; I'll get to those later.
Suppose I have any first-order structure $M$ in some language $L$. Say, $L$ is the language of rings ($+, \times, 0, 1$) and $M$ is the ring $\mathbb{Z}$.
Then $M$ has (of course) many subsets, but some of these subsets are much nicer than others, in the sense of being "describable" using the language $L$. For example, let $E$ be the set of even numbers. Then $E$ is the set of $x$ such that "There is some $y$ such that $x=y+y$." More formally, $E$ is the set of elements $x$ of $M$ such that the statement "there is some $y$ such that $x=y+y$" is a true statement about $M$. This is what is meant by "$M$ satisfies . . . " It's just saying, "... is true in $M$." In particular, being very formal we would write
$$E=\{x: M\models \exists y(x=y+y)\}.$$ The formal definition of "$\models$" is actually somewhat annoying; at first, I think it's better to just think of it informally, so "$M\models \varphi$" means "$\varphi$ is a true statement about $M$." But see here, or any good logic textbook.
A set like this - such that there is a formula $\varphi(x)$ in the language $L$, so that the set is equal to $\{x: M\models\varphi(x)\}$ - is called definable without parameters. Other definable subsets of $M$ include the set of perfect squares, the set of positive numbers (this one takes some work, since we don't have the symbol "$<$"!), and the set of primes.
Note that the definability of a subset of $M$ depends crucially on the language of $M$. For example, consider the structure $M'$ whose underlying set is $\mathbb{Z}$ as before, but whose language is the empty language (no symbols except =). Then no subset of $M'$ is definable without parameters except the whole structure and the emptyset; this is a consequence of the fact, provable by induction, that definable sets are preserved by automorphisms: if $\alpha$ is an automorphism of $M$ and $D$ is a definable subset of $M$, then $\alpha(D)=D$. The claim about $M'$ now follows since every permutation of $M'$ is an automorphism of $M'$.
OK, now what about those $a_i$s? Well, there's a few ways to treat this.
First, given any set $A\subset M$ of a structure in a language $L$, we can consider an expanded language $L_A=L\sqcup\{c_a: a\in A\}$ gotten by adding a new constant symbol for each element of $A$, and the expansion $M_A$ of $M$ gotten by taking $M$, and interpreting the symbol $c_a$ as $a$ for each $a\in A$.
The act of passing from $M$ to $M_A$ is all about adding expressive power. Specifically, more sets are definable in $M_A$ than were definable in $M$! For example, every finite subset of $A$ is now definable in $M_A$; and we might get more, besides. On the other hand, because definitions can only use finitely many symbols, the whole set $A$ might not be definable in $M_A$ (for example, take $M'$ from before and $A=\{evens\}$).
That is, in defining a set, we only use finitely many symbols: for a specific set $D\subset M$, $D$ is definable in $M_A$ iff $D$ is definable in $M_{A_0}$ for some finite $A_0\subset A$.
We say a set $D\subset M$ is definable from parameters (usually, we just say "definable") if, for some $A$, $D$ is a definable subset of $M_A$. Note that by the above paragraph, we can assume $A$ is finite - $A$ is just the set $\{a_0, a_1, . . . , a_n\}$ of your OP!
So then $Def(M)$ is the collection of definable-with-parameters subsets of $M$. Since this is a collection of subsets of $M$, it's a subset of the powerset of $M$.
Alternatively, if you don't want to think of expanding $M$, we can think of a formula $\varphi$ in $n+1$ variables as describing a whole bunch of sets, one for each $n$-tuple of elements of $M$: given the tuple $a_1, . . . , a_n$, we get the set $$\varphi_{a_1, . . . , a_n}=\{m\in M: M\models \varphi(m, a_1, . . . , a_n)\}.$$ Then a set is definable with parameters if it is of the form $\varphi_{a_1, . . . , a_n}$ for some formula $\varphi$ and tuple of elements of $M$ $a_1, . . . , a_n$.
I find this approach more difficult to think about, but it is certainly shorter. On the other hand, one advantage of it is that it connects nicely with definable subsets of higher Cartesian powers: a formula $\varphi$ in $n+1$ variables defines - without parameters - a subset of $M^{n+1}$; then we have that a subset of $M$ is definable-with-parameters iff it is a projection of some definable-without-parameters subset of a higher Cartesian power of $M$. This is kind of nice!
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
Here are some standard examples of definable sets which are not definable over the emptyset in one free variable.
We define $\varphi(\mathfrak{A})=$ the set which is defined by $\varphi$ in a model $\mathfrak{A}$.
$\mathbf{Example}$ $\mathbf{1}$: Let $L=\{E\}$ and let $T$ be the theory of infinitely many equivalence classes, each with infinitely many elements. Let $\mathfrak{A} \models T$. Note that here, the only definable sets are the emptyset and the entire model. However, let us adjoin a constant symbol for some element in each equivalence class. We now consider the definable sets over $(\mathfrak{A},a_i)_{i\in X}$ such that for each $a_i, a_j$ $a_iEa_j \iff i=j $. Now we can actually define each equivalence class in this model. We consider the formula $\varphi_i(x,a_i)=xEa_i$. Therefore, $|\varphi_i(\mathfrak{A})|=|M|$ and $\varphi_i(\mathfrak{A})\cap\varphi_j(\mathfrak{A})=\emptyset \iff i\neq j$. Now, we have infinitely many definable sets, each of coinfinite size, which (pairwise incompatibility) partition the elements of our model.
$\mathbf{Example}$ $\mathbf{2}$: Let $L=\{\leq\}$. We consider $\mathfrak{A}=\{\mathbb{N}+\mathbb{Z};\leq\}$. Our order type is the the natural numbers with a $\mathbb{Z}$-chain on the end. It is easy to show that all definable subsets over the emptyset are either finite or cofinite. Let us consdier the definable sets over $X=\{a\}$ where $a$ is greater than infinitely many elements of our model. What can we now define? Now we can define a coinfinite set. Note that for every element $x \in$ $\mathfrak{A}$, we know that there exists infinitely many elements larger than $x$. This follows since $\mathfrak{A}\equiv\{\mathbb{N};\leq\}$. Now, consider the formula $\varphi(x,a)=x\geq a$. Now $|\mathfrak{A}-\varphi(\mathfrak{A})|=|\varphi(\mathfrak{A})|=\aleph_0$. Therefore, this set, $\varphi(\mathfrak{A})$ was not definable before, but is now definable.
$\mathbf{Antiexample}$ $\mathbf{1}$: Let $L=\{+,\times,0,1\}$ and let $ACF_0$ be the theory of algebraically closed fields of characteristic zero. Let $\mathfrak{A}\models ACF_0$. We consider the definable sets in one free variable. Note that the only thing that you can say (atomically, in one free variable) is either equivalent $p(x)=0$ or $p(x)\neq 0$, where $p(x)$ is a polynomial. Now what are the definable sets? We can define every (algebraic) finite set and every cofinite set (containing all transcendentals in our model). If we have algebraic elements $a_1,...,a_n$, we have a polynomial definable in our language such that $p({\mathfrak{A}})=\{a_1,...,a_n\}$. However, there is no formula that will separate the transcendentals from our cofinite sets, i.e. $\neg p(\mathfrak{A})$ clearly contains every transcendental by definition. Note that to define an infinite set which does not contain any transendentals over any set of parameters (including the using our whole model as parameters) is impossible. Why? We can only say $p(x)=0$ or $\neg p(x)=0$. Since $\neg p(x) =0$ always defines a set with all the transcendental elements, it is useless. Since $p(x)=0$ only defines finitely many elements, then any finite disjunction (i.e. $[p(x)=0]\vee...\vee [q(x)=0]$) defines finitely many elements. Since there are infinitely many algebraic elements, we are done.
$\mathbf{Motivation}$ $\mathbf{1}$: The first type of motivation is classification. A theory $T$ is called strongly minimal if every definable sets in the model with parameters is either finite or cofinite. An example of this include algebraically closed fields of characteristic $p$ (essentially, stongly minimal theories is an anti-example to your question). Clearly classification is important since we can deal with collections of theories instead of working on each theory in particular. But this is just one side of the coin.
$\mathbf{Motivation}$ $\mathbf{2}$: Morely Rank is the other side. Morely Rank, informally, asks "How many infinite collections of pairwise incomparable definable sets are there in your model?". If you want, I can edit my post and define it, however, this can be found in Marker's text, Model Theory: An Introduction. For example, Example 1 has a Morely Rank of 1 (Rank starts at 0). As defined in the example, we can split the model into infinitely many sections, each non-intersecting. Then, we can do this again, and look at each (singleton) element in a particular equivalence class.
$\mathbf{Importance}$: Morely Rank and strongly minimal theories, as classification tools, were vital to the proof of Morley's Categoricity Theorem, namely, for all complete, first-order theories $T$ in a countable language, if $T$ is categorical in some uncountable power, then $T$ is categorical in all uncountable powers.
$\mathbf{Conclusion}$: In first-order logic, the possible definable sets and the number of pairwise incomparable definable sets gives rise to classification which in turns allows one to prove non-trivial theorems.