Your observation that $E(QQ^T) = \operatorname{diag}(k/n,\dotsc,k/n)$ points in the right direction. The expected value of the off-diagonal elements of $QQ^T$ vanishes by symmetry, since flipping the sign of a row of $Q$ preserves $Q^TQ=1$ but changes the sign of the off-diagonal elements of $QQ^T$. The diagonal elements must all be equal by symmetry, and $\operatorname{tr}QQ^T=\operatorname{tr}Q^TQ$ shows that they must be $k/n$.
Then by the cyclic invariance of the trace and the linearity of trace and expectation
$ \begin{eqnarray} E\left(\lVert v\rVert^2\right) &=& E\left(v^Tv\right) \\ &=& E\left(\operatorname{tr}\left(v^Tv\right)\right) \\ &=& \frac nkE\left(\operatorname{tr}\left(u^TQQ^Tu\right)\right) \\ &=& \frac nkE\left(\operatorname{tr}\left(uu^TQQ^T\right)\right) \\ &=& \frac nk\operatorname{tr}\left(E\left(uu^TQQ^T\right)\right) \\ &=& \frac nk\operatorname{tr}\left(uu^TE\left(QQ^T\right)\right) \\ &=& \operatorname{tr}\left(uu^T\right) \\ &=& \operatorname{tr}\left(u^Tu\right) \\ &=& u^Tu \\ &=& \lVert u\rVert^2\;. \end{eqnarray} $
Alternatively, you can argue as follows. Since permuting the columns of $Q$ preserves $Q^TQ=1$, the expected values of the squares of the components of $v$ are all the same by symmetry, so $E(\lVert v\rVert^2)$ is just $k$ times one of these expected values. A component of $v$ is $\sqrt{n/k}$ times the scalar product of a random unit vector with $u$. If we rotate to a basis in which $u$ has only one non-zero component, this scalar product becomes $\lVert u\rVert$ times that component of the random unit vector. By symmetry, the expected value of the square of a component of an $n$-dimensional unit vector is $1/n$, and the result follows.