$\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)\cdots(m-n+1)}{m^n} \\
=\frac{(m-1)\cdots(m-n+1)}{m^{n-1}},
\end{multline*}
whence
\begin{equation}
\PP(N=n)=\PP(N>n-1)-\PP(N>n)
=\frac{(m-1)\cdots(m-n+2)}{m^{n-1}}\,(n-1).
\end{equation}
So,
\begin{multline*}
\mu_k(m):=\E \binom Nk \\
=\frac1{k!}\sum_{n=k}^{m+1}\frac{n-1}{m^{n-1}}\,n(n-1)\cdots(n-k+1)(m-1)\cdots(m-n+2). \tag{1}
\end{multline*}
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"; I have verified numerically that for $m=1,\dots,100$ the latter expression for $\mu_4(m)$ matches the special case of (1) for $k=4$. 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.
