Complexity of finding binomial coefficient which equals to a number
It is not true that $(n-k)^k&lt;{n\choose k}$. For example ${9\choose 2} = 36 &lt; 49 = (9-2)^2$.

I haven't (yet) found a subtle solution using arithmetic properties of the binomial coefficients, however I can suggest a somewhat bruteforce one if that helps :-)

You could, for each $k$, solve for $n$ by taking an initial guess (say $\sqrt[k]{k!\cdot m}$) and using an analytical method such as Newton-Raphson. You want to solve ${n\choose k} - m = 0$. The derivative of the left hand side with respect to $n$ is $(\psi(n+1)-\psi(n-k+1)){n\choose k}$ where $\psi$ is the digamma function, which is easy to compute.

The complexity of a Newton-Raphson search only depends on the complexity of computing the function and its derivative, and the number of digits required for the solution (in our case we just need the closest integer).

So overall for each $k$ the search should be $O(1)$ (assuming, as you seem to have done, that computing a binomial coefficient takes constant time), hence the total complexity for the algorithm using your bounds for $k$ would be $O(\log(m))$.