Let $P$ be a monic polynomial of degree $n$ over $\mathbb Z$. Let $\alpha_1,\dots, \alpha_n$ be its roots, which we view as elements of $\overline{\mathbb Q_p}$. Then all $p$-adic valuations of $P$ are at most
$$ n \left( k -1 + \frac{p}{(p-1)^2}\right)$$
and this is close to sharp.
Proof: Let $m$ be a value on which it attains a large $p$-adic valuation.
For each nonnegative integer $t$, let $$v_t = \sum_{i=1}^n \min( v_p( \alpha_i -m), t)$$
Then $v_t$ is a strictly increasing sequence until it reaches its maximum value of $\sum_{i=1}^n v_p(\alpha_i-m) = v_p(P(m))$. We have $v_0=0$ so $$v_p(P(m)) = \sum_{t=0}^{\infty} ( v_{t+1} - v_t).$$
For each value of $t$ before the maximum, there are two possibilities. Either some value in $[v_t, v_{t+1})$ occurs as $v_p ( P (x))$ for some $x \in \mathbb Z$ or not.
Because none of these intervals contains the maximum, there are at most $k-1$ values of $t$ of the first type. For each one, $v_{t+1} - v_t \leq n$, so these values contribute at most $n(k-1)$ to the sum.
Now let's fix one $t$ of the second type. For any integer $u$ that's congruent to $1$ mod $p$, we have $$v_p ( P (m + p^t u )) =\sum_{i=1}^n v_p ( \alpha_i - m - p^t u ) \geq \sum_{i=1}^n \min ( v_p ( \alpha_i - m ), t) = v_t$$ so $v_p ( P (m+p^t u ) ) \geq v_{t+1}$ by assumption. Thus
$$ v_{t+1} - v_t \leq v_p ( P ( m + p^t u)) - v_t = \sum_{i=1}^n ( v_p ( \alpha_i - m - p^t u ) - \min ( v_p ( \alpha_i - m ), t))$$
The difference $ v_p ( \alpha_i - m - p^t u ) - \min ( v_p ( \alpha_i - m ) $ vanishes unless $v_p ( \alpha_i -m ) =t$ , in which case it is $v_p ( \frac{\alpha_i -m}{p^t} - u ) $. So
$$ v_{t+1} - v_t \leq \sum_{ i \mid v_p (\alpha_i -m)=t} v_p \left( \frac{\alpha_i -m}{p^t} - u \right)$$
This inequality, because it holds for all integers nonzero mod $p$, holds for all $p$-adic numbers nonzero mod $p$. Integrate it over all $p$-adic numbers nonzero mod $p$ (or sum over numbers nonzero mod $p$ in a large interval, divide by the length of the interval, and take the limit.
$$ \frac{p-1}{p} (v_{t+1} - v_t) \leq \sum_{ i \mid v_p (\alpha_i -m)=t} \int_{ u \in \mathbb Z_p^\times} v_p \left( \frac{\alpha_i -m}{p^t} - u \right) du \leq \sum_{ i \mid v_p (\alpha_i -m)=t} \left( \frac{1}{p} + \frac{1}{p^2} + \dots \right) = \sum_{ i \mid v_p (\alpha_i -m)=t} \frac{1}{p-1} $$
because the function $v_p ( \frac{\alpha_i -m}{p^t} - u )$ is at most $1$ restricted to $u$ that are congruent to $\frac{\alpha_i -m}{p^t}$ mod $p$ plus $1$ restricted to $u$ that are congruent to $\frac{\alpha_i -m}{p^t}$ mod $p^2$ plus...
Thus
$$v_{t+1} - v_t= \left| \{ i \mid v_p (\alpha_i -m)=t\}\right| \frac{p} {(p-1)^2} $$
Summing this over all $t$, these terms contribute at most $ n \frac{p}{ (p-1)^2}$ since we can have $ v_p (\alpha_i -m)=t$ for at most one $t$. Adding the contribution of the two types of terms, we get the claim.
Construction:
Let $n = 2 \cdot p^r$ for $r>0$.
Take $$P(m) = \prod_{i=0}^{p^{r}-1} (m - p^{k-1} (i + p^{r-1} \sqrt{p})) (m- p^{k-1} (i-p^{r-1} \sqrt{p})) = \prod_{i=0}^{p^{r}-1} ( (m-p^{k-1} i)^2 -p^{2k+2r-3} )$$
which indeed is monic with integer coefficients.
Then $v_p(P(m))$ takes the value $2 p^r v_p(P (m))$ if $v_p(P(m)) < k-1$. So to show it takes at most $k$ values, it suffices to show it takes the same value at all $m$ with $v_p(m) \geq k-1$. For such $m$, we must have $m$ congruent to $j p^{k-1} \mod p^{ r+ k-1}$ for some $0 \leq j < p^{r}$.
Then
$$v _p ( m- p^{k-1} ( i \pm p^{r-1} \sqrt{p} )) = v_p ( p^{k-1} ( j-i \pm p^{r-1} \sqrt{p} + O ( p^r)))$$
which if $j-i$ has $p$-adic valuation $r$, is $k-1 + v_p(j-i)$ because the $j-i$ term dominates, and if $j-1$ has $p$-adic valuation $r-1$, is $ k-1 + r - \frac{1}{2}$ because the $p^{r-1} \sqrt{p}$ term dominates.
For any $j$, we have $v_p(j-i)=0$ for $p^r - p^{r-1}$ values of $i$, $=1$ for $p^{r-1} - p^{r-2}$ values of $i$, and so on, up to $p$-adic valuation at least $r$ for one value of $i$.
Summing over all $i$, we get $$ \sum_{i=0}^{p^r-1} \left(k-1 + \min \left( v_p (j-i), r-\frac{1}{2} \right) \right) =p^r (k-1) + p^{r-1} + p^{r-2} + \dots + 1 - \frac{1}{2},$$ and doubling to account for signs gives $$v_p ( P(m)) = 2 p^r (k-1) + \frac{2(p^r -1)}{p-1} -1 = n \left( k-1 + \frac{1}{p-1} \right) - O(1),$$ which almost matches our upper bound.
