$\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.