It turns out it is possible to prove a (very very) slightly weaker lower-bound, namely

$\|v\| = \Omega\left(\left(\dfrac{d}{k}\right)^{1/2}n^{1/2-o(1)}\right) \text{ w.p }1-o(1).
$

Moreover, this bound is non-asymptotic, and we only need to asume $d \le n$ (nothing else).

Note that $\|\overline{z}\| = \max_{\|u\| = 1}\overline{z}^\top u$.
Let $\mathcal C_\epsilon = \{u_1,\ldots,u_{N_\epsilon}\} \subseteq \mathbb R^k$ be an $\epsilon$-cover for the $(k-1)$-dimensional unit-sphere $\mathbb S_{k-1}$, with $N_\epsilon \le (1/\epsilon)^k$. For any $u \in \mathbb S_{k-1}$, there exists $u_\epsilon \in \mathcal C_\epsilon$ such that $\|u-u_\epsilon\| \le \epsilon$. A simple covering argument gives

$$
\|\overline{z}\| = \sup_{\|u\| = 1}\overline{z}^\top u \le \sup_{\|u\| = 1} \overline{z}^\top u_\epsilon + \epsilon \|\overline{z}\| \le \sup_{u \in \mathcal C_\epsilon}\overline{z}^\top u + \epsilon\|\overline{z}\|.
$$

Taking $\epsilon=1/2$, we obtain

$$
\|\overline{z}\| \le 2\sup_{u \in \mathcal C_\epsilon}\overline{z}^\top u. \tag{1}
$$

Now, fix a unit-vector $u$ in $\mathbb R^k$, and consider set $f(W):=\overline{z}^\top u = \sum_{i=1}^n y_i\sum_{j=1}^k \psi(x_i^\top w_j)u_j$. It is easy to see that $f:\mathbb R^{d^k} \to \mathbb R$ is $\mathcal C^\infty$ a.e, with gradient given by

$$
\partial_{w_{j,l}} f(W) = u_j \sum_{i=1}^n y_ix_{i,l}\psi'(x_i^\top w_j) = u_j \sum_{i=1}^n y_ix_{i,l}1[\![x_i^\top w_j > 0]\!]\;\forall (j,l) \in [k] \times [d],
$$
and hessian which is zero a.e. Noting that the distribution $\mathcal N(0,1/d)$ of the $w_j$'s satisfies a *Logarithmic Sobolev Inequality* with constant $d^{-1/2}$, Adamczak-Wolf theory for concentration of non-Lipschitz functions (more precisely, **Theorem 1.2** with $D=p=2$) gives,

$$
\begin{split}
\mathbb P(\big||f(W)| - |\mathbb E[f(W)]|\big| \ge t) &\le \mathbb P(|f(W) - \mathbb E[f(W)]| \ge t)\\
&\le 2 \exp(-Cdt^2/\|\mathbb E[\nabla f(W)]\|^2_{Fro}),
\end{split}
\tag{2}
$$

for an absolute constant $C>0$. Now, one computes
$$
\begin{split}
\|\mathbb E[\nabla f(W)]\|^2_{Fro} &= \sum_{j=1}^k\sum_{l=1}^d (u_j \sum_{i=1}^n y_ix_{i,l}\mathbb P(x_i^\top w_j > 0))^2\\
&= \frac{1}{4}\sum_{j=1}^ku_j^2\sum_{l=1}^d(\sum_{i=1}^n y_i x_{i,l})^2 = \frac{1}{4}\|X^\top y\|^2\text{ since }\|u\| = 1.
\end{split}
$$

Thus, except for an event $\mathcal E_n$ of probability $e^{-\Omega(d)}$, we have

$$
\|\mathbb E[\nabla f(W)]\|^2_{Fro} =\frac{1}{4}\|X^\top y\|^2 = \mathcal O(n).
\tag{3}
$$

On the other hand, one computes

$$
\begin{split}
\mathbb E[f(W)] &= \sum_{i=1}^n y_i \sum_{j=1}^k u_j \mathbb E[\psi(x_i^\top w_j)] = \sum_{i=1}^n y_i \sum_{j=1}^k u_j \dfrac{\|x_i\|}{\sqrt{2\pi d}}\\
&=\dfrac{1}{\sqrt{2\pi d}}\cdot (n^+ - n^-) \cdot \sum_{j=1}^k u_j,
\end{split}
$$

where $n^+ := \#\{i \in [n] \mid y_i = 1\}$ and $n^- := \#\{i \in [n] \mid y_i = -1\}$. Thus,
$$
|\mathbb E[f(W)]| = \dfrac{1}{\sqrt{2\pi d}}\cdot |n^+ - n^-| \cdot \left|\sum_{j=1}^k u_j\right| \le \dfrac{1}{\sqrt{2\pi d}}\cdot |n^+ - n^-| \cdot \sqrt{k}.
$$

Using Hoeffding's inequality, it is easy to see that for any $\tau \in (0,n]$, it holds that $|n^+-n^-| \le \sqrt{n\tau}$ except on an event $(y_1,\ldots,y_n) \in \mathcal E_n'$ which occurs with probability $e^{-\Omega(\tau)}$. Thus, conditioned on this event, the previous computation gives w.p $1-e^{-\Omega(\tau)}$

$$
|\mathbb E[f(W)]| = \mathcal O\left(\sqrt{\frac{kn\tau}{d}}\right).
\tag{4}
$$

Let $\mathscr F_n := \mathcal E_n \cap \mathcal E'_n$, an event which occurs with probability at most $e^{-\Omega(d \land \tau)}$.

Plugging the estimates (3) and (4) into (2), and taking $t=\sqrt{kn\tau/d}$, we obtain that conditioned on $\mathscr F_n$ not occurring,

$$
\mathbb P(|f(W)| \ge c\sqrt{kn\tau/d}) \le 2\exp(-Ck\tau).
$$

Taking $\tau = \Omega(n^{2\delta})$ for some small $\delta>0$, and conditioning on $\mathscr F_n$ not occurring, we have

$$
\mathbb P(|f(W)| \ge c\sqrt{kn^{1+2\delta}/d}) \le 2\exp(-C'kn^{2\delta}).
$$

Doing a union bound on (1) and combining with (5), we obtain that: if $d \le n$, then conditioned on $\mathscr F_n$ not occurring, we have $\mathbb P(\|\overline{z}\| \ge c\sqrt{kn^{1+2\delta}/d}) = e^{-\Omega(kn^{2\delta})}$. Thus, by virtue of (*),

$$
\|v\| = \Omega\left(\left(\frac{d}{k}\right)^{1/2}n^{1/2-\delta}\right) \text{ w.p }1-e^{-\Omega(kn^{2\delta})}.
$$

Finally, recalling that $\mathbb P(\mathscr F_n) \le e^{-\Omega(d \land \tau)} = e^{-\Omega(d \land n^{2\delta})}=o(1)$, we obtain (+) via *Bayes' rule*.