For any natural $n$, \begin{multline*} P(N>n)=P(X_1,\dots,X_n\text{ take distinct values })=\frac{m(m-1)\dots(m-n+1)}{m^n} \\ =\frac{(m-1)\dots(m-n+1)}{m^{n-1}}, \end{multline*} whence \begin{equation} P(N=n)=P(N>n-1)-P(N>n) =\frac{(m-1)\dots(m-n+2)}{m^{n-1}}\,(n-1). \end{equation} So, \begin{equation} \mu_k(m):=E\binom Nk=\frac1{k!}\sum_{n=k}^{m+1}\frac{n-1}{m^{n-1}}\,n(n-1)\dots(n-k+1)(m-1)\dots(m-n+2). \end{equation} From here, with the help of Mathematica, I do get \begin{equation} E\binom N2=m. \end{equation}
However, $\mu_4(10)-3\mu_4(9)+3\mu_4(8)-\mu_4(7)=0.0126\ldots\ne0$, so that $\mu_4$ is not a polynomial of degree $4/2=2$. That is, in general the statement that $E\binom Nk$ is a polynomial of degree $k/2$ in $m$ is false.