In fact, the inequality $(**)$ should be the other way around.
As Austin Mohr noted, Stirling's formula comes in handy here. The form that I will use is $n! \sim \biggl(\dfrac{n}{e}\biggr)^n \sqrt{2\pi n}. \tag{1}$ Also, I assume that $m \to \infty$ and that $m - n \to \infty$.
We start by observing that the inequality $(**)$ is equivalent to $\dbinom{m}{n} < 2^{\binom{n}{2} - 1}. \tag{2}$ Since $\dbinom{m}{n} \geq \dfrac{(m - n)^n}{n!},$ we have from $(2)$ that $(m - n)^n < n! 2^{\binom{n}{2} - 1}.$ Plugging in Stirling's formula $(1)$, we have $m^n \biggl(1 - \dfrac{n}{m}\biggr)^n < \biggl(\dfrac{n}{e}\biggr)^n \sqrt{\dfrac{\pi n}{2}} 2^{\binom{n}{2}}.$ Taking $n$th roots, we get $m \biggl(1 - \dfrac{n}{m}\biggr) < \dfrac{n}{e} 2^{\frac{n - 1}{2}} \biggl(\dfrac{\pi n}{2}\biggr)^{1/2n}.$ Finally, observing that $(\frac{\pi n}{2})^{1/2n} / (1 - \frac{n}{m}) \to 1$ as $m$, $n \to \infty$, we end up with $m < \dfrac{1}{e\sqrt{2}} n 2^{n/2},$ as desired.