In another answer, @dohmatob establishes the lower bound $$ \alpha_k(A)\geq\frac{1}{n}\max\Big\{\operatorname{tr}(A),k\lambda_{\operatorname{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_{\operatorname{min}}(G)^2}\bigg]. \end{align*} It is known that $\sigma_{\operatorname{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. Next, equation (4.6) from Tropp's paper on User-friendly tail bounds 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(\mbox{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.
