The answer is YES for $b\geq 2$. For $b=1$, the polynomial is constant. Write $a-b$ in base-$b$ representation. We have $${a-b}_{b}={\overline{k_nk_{n-1}\dots k_2k_1k_0}}_{b}\implies a-b=k_nb^n+k_{n-1}b^{n-1}+\cdots+k_1b+k_0$$Keep in mind that $n\geq 1$ because $a-b\geq b$. Consider $P(x)=k_nx^n+k_{n-1}x^{n-1}+\cdots+k_1x+k_0$. Note that its coefficients are indeed from the set $\{0,1,2,\dots,b-1\}$. We have $$P(b)=a-b\mid P(a)-P(b)\implies P(b)\mid P(a).$$Lastly, the degree of $P$ is $n\geq 1$, so $P$ is not constant, as desired.

Yes (for $b \geq 2$; $b=1$ is stupid). By the existence of base-$b$ representation we can let $P(b)=a-b$, and by $a \geq 2b$ this polynomial cannot be constant, so it satisfies the conditions. Furthermore, $$P(b)=a-b \mid P(a)-P(b) \implies P(b) \mid P(a).~\blacksquare$$

very funny solved with Kanav