In another answer, @dohmatob establishes the lower bound
$$
\alpha_k(A)\geq\frac{1}{n}\max\Big\{\operatorname{tr}(A),k\lambda_{\max}(A) \Big\}.
$$
In what follows, we show that this bound is near-optimal for general $A$ in the regime where $k$ is at most a fraction of $n$.

Let $\Lambda$ denote the diagonal matrix of eigenvalues of $A$, and let $G$ denote an $n\times k$ matrix with iid $N(0,1)$ entries. Submultiplicativity gives
\begin{align*}
\alpha_k(A)
&=\alpha_k(\Lambda)
=\mathbb{E}\|(G^\top G)^{-1/2}G^\top\Lambda G(G^\top G)^{-1/2}\|_{2\to2}\\
&\leq\mathbb{E}\Big[\|(G^\top G)^{-1/2}\|_{2\to2}\cdot\|G^\top\Lambda G\|_{2\to2}\cdot\|(G^\top G)^{-1/2}\|_{2\to2}\Big]
=\mathbb{E}\bigg[\frac{\|\Lambda^{1/2}G\|_{2\to2}^2}{\sigma_{\min}(G)^2}\bigg].
\end{align*}
It is known that $\sigma_{\min}(G)\sim\sqrt{n}-\sqrt{k}$ when $n$ and $k$ grow proportionately, and there are nonasymptotic results of this flavor, too; see [Vershynin's survey][1]. Next, equation (4.6) from Tropp's paper on [User-friendly tail bounds][2] implies that (with $B := \lambda^{1/2} \otimes 1_n$, where $\lambda \in \mathbb R^n$ is the vector of eigenvalues of $A$)
$$
\begin{split}
\|\Lambda^{1/2}G\|_{2\to2}^2 = \|B \circ G\|_{2 \to 2}^2
&\leq 2\log(\tfrac{n+k}{\epsilon})\cdot\max(\|\lambda^{1/2}\|^2_2,k\|\lambda^{1/2}\|_\infty^2)\\
&= 2\log(\tfrac{n+k}{\epsilon})\cdot\max(\operatorname{trace}(A),k\lambda_\max(A))
\end{split}
$$
with probability $\geq1-\epsilon$. One may combine these estimates to show that @dohmatob's lower bound is tight up to log factors.


  [1]: https://arxiv.org/abs/1011.3027
  [2]: https://arxiv.org/abs/1004.4389