For simplicity, let $p$ be an odd prime. Let $P(X) \in \mathbf{Z}_p[X]$ be a distinguished polynomial.
Suppose $\mathrm{ord}_p(P(u^k-1))$ is bounded as $k$ varies in the whole integer. Suppose there exist positive integers $k, k^{\prime}$ such that $\mathrm{ord}_p(P(u^k-1)) \neq \mathrm{ord}_p(P(u^{k^{\prime}}-1))$, can we prove that $P(X)$ has zero in $\mathbf{Z}_p$ and make the assumption of bounded failed? Where $u=1+p$. And what about $P(X)$ is the Iwasawa polynomial defining $p$-adic $L$-function, does it has zero in $\mathbf{Z}_p$?
I have no insight concerning your first question. Why do you think that the condition $ord_p P(u^k - 1) \neq ord_p P(u^{k'} - 1)$ should imply the existence of a zero of $P(X)$ ? Or is it just wishful thinking ? Given a power series $f \in \mathbf Z_p[[X]]$, there exist general considerations about its zeroes and the $p$-adic maximum principle (see e.g. the report by Hugo Castillo on « Kubota-Leopoldt’s $p$-adic $L$-functions », thm. 5.1.2 of chap. 5 on « The compact-open topology »), but they are too general to be of use here.
A little more is known about the Iwasawa power series $f_\chi (X)$ which enters the definition of the Kubota-Leopoldt function $L_p (s, \chi)$. By construction, $L_p (s, \chi)$ is identically null if the Dirichlet character $\chi$ is even. If $\chi$ is odd, it can be shown as an exercise that $L_p (s, \chi)=0$ iff $\chi\omega^{-1}(p) = 1$, where $\omega$ is the so called Teichmüller character, which gives the Galois action on the $p$-th roots of unity. But note that in general, a zero of the series $f_\chi (X)$ will not yield a corresponding zero of the function $L_p (s, \chi)$ (numerical counterexamples computed by Wagstaff , circa 1982). Yet a precise relationship can be established by modifying suitably $s$ and $\chi$ in the $L_p$-function (Childress & Gold, Acta Arithmetica, 1987).
The zeroes of the Iwasawa power series are more readily computed because, thanks to the Main Conjecture ( = the theorem of Mazur-Wiles), $f_\chi (X)$ has an algebraic meaning : roughly speaking, it is the « characteristic series » (in the sense of linear algebra) which describes the Galois action on the inverse limit of adequate $p$-class groups along the cyclotomic extension obtained by adjoining to $\mathbf Q$ all the $p^n$-th roots of unity. This does not mean that all its zeroes are known. But « special non-zeroes » have a particular arithmetic meaning. Example : replacing $\mathbf Q$ by a totally real number field $K$, the fact that $0$ is not a zero of an adequate generalization of the « characteristic series » above is equivalent to the validity of the celebrated Leopoldt conjecture for $K$.