As a side issue I'd be interested in knowing how you use $N$ quantifiers to prove well foundedness of an ordinal notation for a stack of $\omega$'s $N$ layers high.
I set myself this as a challenge a few years ago when I was learning this material; here is the solution I came up with. I hope there aren't any bugs.
Let's first check that we agree on the setup:
Let $X$ be an ordered set with order relation $\leq$. Then $\omega^X$ is the set of functions $X \to \omega$ such that all but finitely many elements of $X$ map to $0$. We'll write elements of $\omega^X$ to look like sequences: $(a_i)_{i \in X}$, where $i$ maps to $a_i$. We have $(a_i) > (b_i)$ if there is an index $d$ with $a_d > b_d$ and $a_e = b_e$ for $e > d$. (Expressing this in PA requires tons of $\beta$-encoding, but I am going to assume you are already completely comfortable with that and brush those issues under the rug.) The symbol $0$ will denote the minimal element of $\omega$, the minimal element of $X$ and the minimal element of $\omega^{X}$; which one I mean should be clear from context.
Let $\phi$ be a first order statement with a free variable $x$ ranging over $X$. Let $I(x,X,\phi)$ denote the statement: $$ \left( \exists x \in X : \phi(x) \right) \implies \exists z \in X : \phi(z) \ \wedge \ \forall w \in X : \phi(w)\! \implies \! w \geq z $$ In other words, if any element of $X$ obeys $\phi$, then there is a least element of $X$ obeying $\phi$. We say that PA proves $X$ is well-ordered if, for any $\phi$, PA proves $I(x,X,\phi)$.
We want to show that, if PA proves that $X$ is well-ordered, then PA also proves that $\omega^X$ is well ordered.
The strategy of the proof is the only thing it could be. I will describe a recipe which, given a first order sentence $\phi(x)$, with $x$ ranging over $\omega^X$, produces a first order sentence $\phi'(x')$ with $x'$ ranging over $X$. I'll then show that $I(x', X, \phi')$ implies $I(x,\omega^X, \phi)$. The sentence $\phi'$ will have three occurrences of $\phi$: One preceded by $\forall \neg$, one preceded by $\exists$ and one preceded by $\exists \forall \neg$. If $\phi$ is in $\Sigma_n$, then these are in $\Pi_n$, $\Sigma_n$ and $\Sigma_{n+1}$ respectively. I think this shows that this construction takes $\Sigma_n$ to $\Sigma_{n+1}$ (but I must admit that I am not fully confident in this argument.)
Write $\omega \uparrow n$ for a towers of $\omega$'s stacked $n$ high. Then this argument reduces proving $I(x,\omega \uparrow n, \phi)$ to proving $I(x', \omega \uparrow (n-1), \phi')$, and the reduces that to $I(x'', \omega \uparrow (n-2), \phi'')$ etcetera, until we finally reach $I(x^{n-1}, \omega, \phi^{n-1})$. In the process, we have added turned a $\Sigma_k$ statement into a $\Sigma_{k+n}$ statement. Of course, $I(x^{n-1}, \omega, \phi^{n-1})$ is an axiom of PA, so we will then be done.
For readability, I'll change the notations $\phi'$ and $x'$ to $\delta$ and $d$. In general, I will try to use letters from the beginning of the alphabet for elements of $X$ and letters from the end for elements of $\omega^X$.
Here is the crucial sentence $\delta(d)$: $$\left( \exists x \in \omega^X : \phi(x) \right) \implies \exists z \in \omega^X : \phi(z) \ \wedge \ \forall w \in \omega^X : \phi(w)\! \implies \! \left( w \geq z \ \vee \ \forall_{e \geq d} : w_e=z_e \right) $$ In other words, $\delta(d)$ is essentially the induction claim $I(x,\omega^X, \phi)$, but we are allowed to have $w<z$ as long as $w$ and $z$ agree on the part of $X$ past $d$.
Rewritten without $\implies$, this is of the form $$\forall_x \neg \phi(x) \vee \exists_z \left( \phi(z) \wedge \forall_w \neg \phi(w) \vee (\mbox{stuff without }\ \phi) \right).$$ So $\delta$ precedes $\phi$ with $\forall \neg$, with $\exists$ and with $\exists \forall \neg$ as promised.
What remains is to show that $I(d, \delta, X)$ implies $I(x, \phi, \omega^X)$. You might enjoy doing this yourself more than reading my solution.
If $\phi(x)$ is false for all $x$, then $I(x, \phi, \omega^X)$ is vacuously true. So we may assume that there is an $x$ obeying $\phi(x)$.
Choose $d_1$ large enough that $x_e=0$ for all $e \geq d_1$. Then $\delta(d_1)$ is true because, for any $w \in \omega^X$, we either have $w \geq x$ or $ \forall_{e \geq d_1} : w_e=0$. So there is some $d$ which makes $\delta$ true. Let $d$ be the least element of $X$ which makes $\delta$ true.
If $d=0$, we are done, since $\delta(0)$ is precisely $I(x,X, \phi)$. So assume for the sake of contradiction that $d>0$.
Let $\bar{z} \in \omega^X$ be the element which is promised to exist according to $\delta(d)$. There are only finitely many $i$ for which $\bar{z}_i$ is nonzero. Let $c$ be the greatest such $i$ which is less than $d$. So $\bar{z}$ looks like $$(\ldots, 0,0,0,\bar{z}_c, 0,0, \ldots, 0,0, \ldots, 0,0, \bar{z}_d, 0, 0, \ldots).$$ If $\bar{z}_i$ is zero for all $i<d$, then take $c=0$. Our goal is to prove $\delta(c)$; this will contradict the minimality of $d$ and thus complete the proof.
Let $\ell$ be the smallest element of $\omega$ such that there exists $y \in \omega^X$ with the following properties: $$\phi(y) \ \wedge \ y_c=\ell \ \wedge \ \forall_{e > c} : y_e = \bar{z}_e$$ There is at least one such $\ell$, since we can take $y=\bar{z}$ and $\ell = \bar{z}_c$, so there is a least such $\ell$ because $\omega$ is well ordered. Let $y$ be the element of $\omega^X$ as above.
I claim that taking $y$ in place of $z$ makes $\delta(c)$ true. Let $w$ obey $\phi(w)$. So either $w \geq \bar{z}$ or $\forall_{e \geq d} w_e = \bar{z}_e$. We must show that either $w \geq y$ or $\forall_{e \geq c} w_e = y_e$.
Case 1 There is some $e \geq d$ with $w_e \neq \bar{z}_e$.
Then $w > \bar{z}$. Since $\forall_{f \geq d} : y_f=\bar{z}_f$, we also have $w > y$, as desired.
Case 2 For all $e \geq d$ we have $w_e = \bar{z}_e$. However, there is an $e$ with $c < e < d$ and $w_e \neq \bar{z}_e$.
For $e$ in this range, $\bar{z}_e = y_e = 0$. So $w > y$, as desired.
Case 3: For all $e > c$, we have $w_e = \bar{z}_e$. However, $w_c \neq y_c$.
By the construction of $y$, we have $w_c > y_c$ and thus $w>y$.
Case 4: For all $e \geq c$, we have $w_e =y_e$.
This is the other case in which $\delta(c)$ is true.
We have now proved that $\delta(c)$ is true, contradicting that $d$ was minimal. So, instead, $d$ was $0$. As described above, this concludes the proof. $\square$.
I'm afraid I don't understand cut elimination, but Will Sawin suggests above that this is also an answer to your main question.