What's the degree of $\binom{x}{k}$?
Partial answer: the function $$ n \mapsto \binom{2n}{n} $$ is not a polynomial in $n$. By Stirling's approximation,
$$ \binom{2n}{n} = \frac{(2n)!}{(n!)^2} \sim \frac{\sqrt{4 \pi n} (2n/e)^{2n}}{2 \pi n (n/e)^{2n}} = \frac{4^n}{\sqrt{\pi n}} $$
which is exponential growth. In particular the function grows faster than any given polynomial in $n$.
See that for $k(x)<\frac x2$: $$ (\frac{x}{k(x)})^{k(x)}\leq\binom{x}{k(x)}\leq (\frac{xe}{k(x)})^{k(x)}. $$ Now some examples:
$k=px$ for $p\in(0,\frac 12)$. $$ (\frac{1}{p)})^{pn}\leq\binom{x}{k(x)}\leq (\frac{e}{p})^{np}, $$ which shows that the function behaves exponentially.
$k$ is constant. $$ (\frac{x}{k})^{k}\leq\binom{x}{k(x)}\leq (\frac{xe}{k})^{k}. $$ Then of course the function behaves as a polynomial.
In other words, by looking at : $$ (\frac{x}{k(x)})^{k(x)}\leq\binom{x}{k(x)}\leq (\frac{xe}{k(x)})^{k(x)}. $$ one can say something about $f(x)$ by looking at $(\frac{x}{k(x)})^{k(x)}$.
To see whether asymptotically the function acts like a polynomial, we can look at: $$ K=\lim_{x\to\infty}\frac{\log\binom{x}{k(x)}}{\log x}. $$ $K$ gives the degree of the asymptotic polynomial.
For instance let's pick $k=p\log x$ for some positive constant $p$:
$$ (\frac{x}{p\log(x)})^{p\log(x)}\leq\binom{x}{k(x)}\implies\\ \lim_{x\to\infty}\frac{\log(\frac{x}{p\log(x)})^{p\log(x)} }{\log x} \leq K=\lim_{x\to\infty}\frac{\log\binom{x}{k(x)}}{\log x}. $$ But then the limit of the left hand side goes to infinity, showing that this will not be polynomial. As a matter of fact, the function behaves as $x^{p\log(x)}$ asymptotically.
You can start to play with other choices of $k(x)$.