$\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\B}{\mathcal B}
\newcommand{\F}{\mathcal F}
\newcommand{\X}{\mathcal X}
\newcommand{\ep}{\epsilon}
\newcommand{\la}{\lambda}
\newcommand{\si}{\sigma}
\newcommand{\Si}{\Sigma}
\renewcommand{\c}{\circ}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\E}{\operatorname{\mathsf E}}
\newcommand{\PP}{\operatorname{\mathsf P}}$

For any natural $n$, 
\begin{multline*}
	\PP(N>n)=\PP(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}
	\PP(N=n)=\PP(N>n-1)-\PP(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. 

Let us now show that $\mu_4(m)$ is not a polynomial in $m$ of any degree. Let  $X_m$ be a random variable (r.v.) with the Gamma distribution with parameters $m$ and $1$, so that $X_m$ has the distribution of the sum of $m$ iid standard exponential r.v.'s, each of those r.v.'s with mean $1$. Then, by the central limit theorem, $\PP(X_m>m)\to1/2$ as $m\to\infty$.   
An expression for $\mu_4(m)$ for any natural $m$ (also obtained with the help of Mathematica) is 
$\frac{1}{3} m \left(-2 e^m m E_{1-m}(m)+m+1\right)$, where $E_n(z)=\int_1^\infty t^{-n}e^{-tz}\,dt$ is "the exponential integral function". So, if $\mu_4(m)$ were a polynomial in $m$, then so would be $e^m m^2 E_{1-m}(m)$. But 
\begin{multline*}
	e^m m^2 E_{1-m}(m)=e^m m^2 \frac1{m^m}\int_m^\infty u^{m-1}e^{-u}du
	=m\,\frac{e^m m!}{m^m}\,\PP(X_m>m) \\ 
	\sim m\,\sqrt{2\pi m}\,\frac12 
\end{multline*}
as $m\to\infty$, 
by Stirling's formula and because $\PP(X_m>m)\to1/2$. 
So, $e^m m^2 E_{1-m}(m)$ cannot be a polynomial in $m$. Thus, $\mu_4(m)$ is not a polynomial in $m$, of any degree.