Your formula is correct.
Let $Y^{(n)}_j:=\#\{i\leq n: X_i=j\}$. Then, $Y^{(n)}=(Y_1^{(n)},\dots,Y_k^{(n)})$ can be viewed as a sum of $k$-dimensional i. i. d. random variables, with terms uniform among $(1,0,\dots,0)$, $(0,1,\dots,0)$, .... Note that $$\mathbb{E}Y^{(n)}=\left(\frac{n}{k},\dots,\frac{n}{k}\right),$$ and by Central Limit theorem, $\frac{1}{\sqrt{n}}(Y^{(n)}-\mathbb{E}Y^{(n)})$ converges in distribution to the $k$-dimensional Gaussian $\mathcal{N}(0,\Sigma)$ with covariance matrix given by $\Sigma_{ii}=\frac{1}{k}-\frac{1}{k^2}$, $\Sigma_{ij}=-\frac{1}{k^2}$ for $i\neq j$.
The minimum of the coordinates is a continuous function on $\mathbb{R}^k$. If it were bounded, we could conclude straight away that $$ \frac{1}{\sqrt{n}}\left(\min_{1\leq i\leq k}\mathbb{E}Y^{(n)}_i-\frac{n}{k}\right)=\mathbb{E}\min_{1\leq i\leq k}\left[\left(\frac{1}{\sqrt{n}}(Y^{(n)}-\mathbb{E}Y^{(n)})\right)\right]_i\to \mathbb{E}\min_{1\leq i\leq k}[\mathcal{N}(0,\Sigma)]_i, $$ which is equivalent to your formula. To complete the proof, you can, for example, truncate the minimum of the coordinates to make it bounded, and then apply Chernoff's bounds to show that the probability to end up in a truncated part is exponentially small as the cut-off goes to infinity, uniformly in $n$.