Are existentially defined subsets of affine algebraic sets unions of a finite number of affine algebraic sets?

Here's an example showing that $S$ is not always a finite union of algebraic sets. Let $Z$ be the zero locus of the single polynomial $x_1x_2 - 1$. Then $S = \mathbb{A}^1\setminus \{0\}$.

What is true is that $S$ is always a finite union of sets defined by finitely many polynomial equations (basic Zariski closed sets) and negated equations (basic Zariski open sets). Such a set is called a constructible set, and the fact that the projection of a Zariski-closed set (or more generally a constructible set) is a constructible set is known as Chevalley's theorem in algebraic geometry.

The $S$ in the example above is defined by the single negated equation $x_1\neq 0$.

As a logician, I prefer to think of this in terms of quantifier-elimination in the theory of algebraically closed fields. This result, due to Tarski, says that a subset of $K^n$ ($K$ algebraically closed) defined by a first-order formula (built up from polynomial equations by finite Boolean combinations and quantifiers) can actually be defined without quantifiers. The set $S$ in your question is defined by the first-order formula $$\exists x_n\, \bigwedge_{i = 1}^k f_i(x_1,\dots,x_n) = 0.$$

Putting the quantifier-free formula we get from quantifier-elimination in disjunctive normal form, it looks like $$\bigvee_{i = 1}^n \bigwedge_{j = 1}^m \varphi_{ij}(\overline{x}),$$ where each $\varphi_{ij}(\overline{x})$ is $p_{ij}(\overline{x}) = 0$ or $p_{ij}(\overline{x})\neq 0$ for some polynomial $p_{ij}$. This is explicitly a finite union of sets defined by finitely many polynomial equations and negated equations.

The operation is called projection. Tbe first-order theory of the complex field (which is the same as the first-order theory of algebraically closed fields of characteristic $0$) admits quantifier elimination. This means that $\exists x_n (x_1, \ldots, x_n) \in Z$ is equivalent to a propositional combination of primitive formulas of the form $p_j(x_1, \ldots, x_n) = 0$ for some finite set of polynomials $p_j$. Hence $A$ can be obtained from a finite set of algebraic sets using union, intersection and complement.

[Aside: analogous results hold over the real field, in which case the definable sets are called semi-algebraic sets and the primitive formulas also include formulas of the form $p_j(x_1, \ldots, x_n) > 0$].