Suppose the contrary and let $k={\rm deg}(P)$. Notice that $m! <m^m = e^{m\log m}$ yielding $e^{n\log 2}<e^{m\log m}$. This gives $m\log m>n\log 2$. Next, note that $P(n)<n^{k+1}$ for all $n$ large, so $v_2(P(n)) <\log_2(n^{k+1}) = (k+1)\log_2 n$. At the same time, it is not hard to verify that $v_2(m!)\ge m/2$ for all $m$ large, so $(k+1)\log_2 n > v_2(P(n)) = v_2(2^n+P(n)) \ge m/2$. As $m\log m>n\log 2$, namely $m=\Omega(n/\log n)$, the latter bound is clearly impossible for all $n$ large, completing the proof.