ZF construction of the Kleene plus Given a non-empty set $A$, a (non-empty) string of $A$ is a tuple $(a_1,a_2,...,a_n) \in A^n$, where $a_j \in A$, $\forall j \in \{ 1,2,...,n \}$, for some $n \in \mathbb{N}^*$.
The Kleene plus of $A$, informally, is a set $\displaystyle A^{+} = \bigcup_{n=1}^{\infty} A^n$. It is the set of all tuples of elements of $A$. My question is: within the ZF axiomatics, how can I ensure that this set exists? How to build it?
 A: The typical way of dealing with questions like this is via a version of the recursion theorem. (This link to Wikipedia discusses a particular case.)
Applications of the recursion theorem typically use replacement in an essential way. Recall that one can state replacement as the schema asserting that if $\varphi(x,y)$ is a formula of set theory that is functional, meaning that for any $x$ there is exactly one $y$ such that $\varphi(x,y)$, then for any set $X$ there is a set $Y$ such that for any $x\in X$ there is a $y\in Y$ such that $\varphi(x,y)$. Informally: $\varphi$ defines a function, and the axiom asserts that the image of a set under a function is a set.
For example, let $\varphi(x,y)$ be the statement that $y=\mathcal P(x)$ is the power set of $y$. Certainly, $\varphi$ is functional, thanks to the power set axiom (and extensionality). We use this to verify that $Z=\{\mathcal P^n(A)\mid n<\omega\}$ exists, where $\mathcal P^n(A)$ is the result of iterating the power set operation on $A$ precisely $n$ times. 
(By the way, $\omega$ exists using the axiom of infinity and comprehension. I will omit "routine" details such as this in the remainder.)
In effect, and this is how most proofs by recursion work, we can for each $n<\omega$ verify that there is an $n$-approximation to $Z$. In this case, this means a function $f$ with domain $n$ such that for all $m<n$, $f(m)=\mathcal P^m(A)$. More formally, if $n>0$ then $f(0)=A$, and for any $m$, if $m+1<n$, then $f(m+1)=\mathcal P(f(m))$. The proof that $n$-approximations exists is a straightforward induction. Using induction again, we check that if $m<n$ then the restriction of any $n$-approximation to domain $m$ is an $m$-approximation, and that for any $n$ there is at most one $n$-approximation (and therefore there is precisely one). 
OK. Now let $\varphi(x,y)$ state that either ($x=n+1$ is a positive integer, and $y$ is $f(n)$, where $f$ is some (any) $x$-approximation), or else ($x=0$ or $x\notin\omega$, and $y=0$). By replacement, $Z$ exists (use replacement with $X=\omega\setminus\{0\}$, and comprehension). 
A very similar argument gives us that for any set $A$, the set $T=\{A^n\mid n<\omega\}$ exists, and now the union axiom gives us the existence of $A^+$.
Note how recursion works: Given an iterative process, to ensure that the result of the $n$-th iteration exists, we actually exhibit a function that traces its whole history. In the example you are interested in, we only need functions with finite domain. In more elaborate instances, we may need functions with infinite (transfinite) domain. For example, this is how one can ensure that the levels $V_\alpha$ of the cumulative hierarchy, or the infinite cardinals $\aleph_\alpha$ ($\alpha\in\mathsf{ORD}$) exist.
