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.