Let me try to give some input. So first of all, this definition appears in a proof, so it should be understood in the context of the proof. The $E$ is fixed in the statement of the lemma and thus it is not quantified over in the definition, so what simple means in the proof maybe should be called $E$-simple and being $E$-simple can be different from being $F$-simple for $E\neq F$.
Regarding your second question, in the definition it is not required that the equivalent $\Sigma_0$-formula is uniform in the structures. To finish the proof, one only needs that all $\operatorname{rud}_E$-functions are simple in this sense (as this is quite tedious to do, this statement was packaged as an exercise). The uniformity is not relevant. Anyhow, doing this exercise reveals that for $\operatorname{rud}_E$-functions these formulas can be chosen uniformly. Indeed even more is true: In the same way as one can associate natural numbers to first order formulas by looking at how they are build from the atomic formulas and the connectives, one can do this with rudimentary functions. There is then a recursive map $\eta:\operatorname{Fml}_{\in, E}\times\omega\rightarrow\operatorname{Fml}_{\in, E}$ so that whenever $f$ is $\operatorname{rud}_E$ and $\varphi$ is a $\Sigma_0$ $\{\in, E\}$-formula then $\varphi(f(v_0, \dots, v_n), w_0, \dots , w_m)$ is equivalent to $\eta(\varphi, k)(v_0, \dots, v_n, w_0,\dots, w_m)$ over any transitive $\operatorname{rud}_E$-closed structure, where $k$ is the natural number associated to $f$. [Again, E is fixed here]
Lastly, the reason why one quantifies over not just all transitive but moreover $\operatorname{rud}_E$-closed strucures is simply that the question whether $\varphi(f(v_0, \dots, v_n), w_0, \dots , w_m)$ is equivalent to $\psi(v_0, \dots, v_n, w_0, \dots , w_m)$ over a structure $\mathcal M=(M, \in, E)$ only makes sense if $M$ is closed under $f$. It means
$$\text{for all }x_0,\dots, x_n, y_0,\dots y_m\in M\ \mathcal M\models \varphi(f(x_0, \dots, x_n), y_0, \dots , y_m)\Leftrightarrow\psi(x_0, \dots, x_n, y_0, \dots , y_m)$$
after all.
First, we can strenghen $(\ast)$ a bit in the following sense: If $F$ satisfies the same assumption as $E$ then $$\mathcal P(U)\cap\operatorname{rud}_{E, F}(U\cup\{U\})=\mathcal P(U)\cap\bar\Sigma_\omega^{(U, \in, E, F)}$$
where $\operatorname{rud}_{E, F}$ closes under functions that are rudimentary in $E$ or $F$.
You can see that even with this relaxed assumption we cannot immediately apply $(\ast)$ to calculate $\mathcal P(J_{\alpha}[E])\cap J_{\alpha+\omega}[E]$ as elements of the form $(\alpha, x)\in E$ are not in $J_\alpha[E]$. This is why we need to consider $E_\alpha$. The following holds true:
$$\mathcal P(J_\alpha[E])\cap J_{\alpha+\omega}[E]=\mathcal P(J_\alpha[E])\cap\operatorname{rud}_{E|\alpha, E_\alpha}(J_\alpha[E]\cup\{J_\alpha[E]\})=\mathcal P(J_\alpha[E])\cap\bar\Sigma_\omega^{(J_\alpha[E],\in, E|\alpha, E_\alpha)}$$
The second equality is true by the revised version of $(\ast)$ above, noting that $E_\alpha\subseteq J_\alpha[E]$. For the first equality we simply observe that $$J_{\alpha+\omega}[E]=\operatorname{rud}_E(J_\alpha[E]\cup\{J_\alpha[E]\})=\operatorname{rud}_{E|\alpha+1}(J_\alpha[E]\cup\{J_\alpha[E]\})=\operatorname{rud}_{E|\alpha, E_\alpha}(J_\alpha[E]\cup\{J_\alpha[E]\})$$
Here the first equality is by definition, the second one holds as in general
$$\operatorname{rud}_E(U\cup\{U\})=\operatorname{rud}_{E\cap V_{\operatorname{rank}(U)+\omega}}(U\cup\{U\})$$
for transitive $U$ and $E\cap V_{\alpha+\omega}=E|\alpha+1$. Finally, we argue that the last equality holds: For $\subseteq$ note that both $E|\alpha$ and $E_\alpha$ are rudimentary in $E$ over $J_{\alpha+\omega}[E]$. Similar for $\supseteq$, $E|\alpha+1$ is rudimentary in $E|\alpha, E_\alpha$ over $\operatorname{rud}_{E|\alpha, E_\alpha}(J_\alpha[E]\cup\{J_\alpha[E]\})$.
Finally I want to mention that it is definately possible that
$$\mathcal P(J_\alpha[E])\cap \bar\Sigma_\omega^{(J_\alpha[E],\in, E)}\subsetneq\mathcal P(J_\alpha[E])\cap J_{\alpha+\omega}[E]$$
It is a nice exercise to come up with such an example. (Hint: there are some with $\alpha=\omega$)
Best Answer
Part of your confusion seems to be caused by a(n) (common) abuse of notation.
Let $N$ be an acceptable (amenable suffices) $\mathcal{J}$-structure. Then there is a uniformly definable $\Sigma_1$-Skolem function for $N$ -- call it $h_N$. I.e. in a fixed (recursive) enumaration $(\phi_n \mid n < \omega)$ of all $\Sigma_0$-formulae in the language of $N$, we have, for all $\vec{p} \in N$ $$ N \models \exists x \phi_n[x,\vec{p}] \iff h_N(n, \vec{p}) \text{ is defined and } N \models \phi_n[h_N(n, \vec{p}), \vec{p}]. $$
Let us now try to understand what's going on with $\sigma^*$:
$$ W^{\nu,p}_M = \mathrm{cHull}_{\Sigma_1}^M(\nu \cup (p \setminus (\nu + 1)) $$ is the transitive collapse of the $\Sigma_1$-hull of $M$ over $\nu \cup (p \setminus (\nu + 1))$. In particular, the Mostowski collapse
$$ \sigma \colon W^{\nu,p}_M \to M $$ is $\Sigma_1$-elementary, so that $W^{\nu,p}_{M}$ is itself an acceptable $\mathcal{J}$-structure (as this is a $\mathcal{Q}$-property).
Claim. $\bar{p} := \sigma^{-1}(p \setminus (\nu + 1))$ is a very good parameter of $W^{\nu,p}_M$.
Proof. Let $x \in W^{\nu, p}_M$. Then $\sigma(x) \in \mathrm{Hull}_{\Sigma_1}^{M}(\nu \cup (p \setminus (\nu + 1) ) \prec_1 M$. Hence there is some $\xi < \nu$ and some $n < \omega$ such that $\sigma(x) = h_M(n, (\xi, (\xi, \sigma(\bar{p})))$.
By the uniform definability of $h_N$ (using that $\sigma$ is $\Sigma_1$-preserving and $\sigma \restriction \nu = \mathrm{id}$), it follows that $x = h_{W^{\nu, p}_M}(n, (\xi, \bar{p}))$. Q.E.D.
Now define, for all $n < \omega$ and all $\xi < \nu$, $$ \sigma^* \colon W^{\nu, p}_M \to W, h_{W^{\nu, p}_M}(n, (\xi, \bar{p})) \mapsto h_W(n, (\xi, r)). $$
It is here that the abuse of notation took place: People often drop the natural number parameter when talking about Skolem functions of $\mathcal{J}$-structures. Probably because they think about the generated hulls and not the actual Skolem functions when writing down these kinds of arguments.
Exercise. $\sigma^*$ is a total, well-defined, $\Sigma_0$-elementary embedding.
(Hint: You need to use that $(W,r)$ is a generalized witness.)
Exercise. If we let $\alpha = \sup h_W(\nu \cup \{r \}) \cap \mathrm{Ord})$, then $$ \sigma^* \colon W^{\nu, p}_M \to \mathcal{J}^W_{\alpha} (\dagger) $$ is $\Sigma_0$-elementary and cofinal. Therefore it is $\Sigma_1$-elementary.
$(\dagger)$ For an acceptable $\mathcal{J}$ structure $N$ and $\alpha \le N \cap \mathrm{Ord}$, $\mathcal{J}^N_{\alpha}$ is the $\alpha$-th level of $N$ in its $\mathcal{J}$-hierarchy, i.e. if $N = (J_{\beta}^A; \in, A)$, then $\mathcal{J}^{N}_{\alpha} = (J_{\alpha}^A; \in, A \cap J_{\alpha}^A)$.