Your construction is optimal, that is, the degree of $f$ is always at least $2p^{k-1}-1$. Note that if $m,x$ have $p$-base expansions $m=\sum_{i}m_i p^i$, $x=\sum_{i}x_i p^i$, we have $\binom{x}{m}\equiv \prod \binom{x_i}{m_i} \pmod p$ by Lucas' theorem, and any integer-valued polynomial is an integer linear combinations of binomials $\binom{x}{m}$ (whose result is it, by the way?). So your question is essentially about polynomials in $k$ variables $x_0,\dots,x_{k-1}$ over $\mathbb{F}_p$, which are reduced (have degree at most $p-1$ in each variable). Assume that degree of $f$ is strictly less than $2p^{k-1}-1$. It means that the corresponding polynomial $F\in \mathbb{F}_p[x_0,\dots,x_{k-1}]$ is at most linear in $x_{k-1}$ and its coefficient of $x_{k-1}x_0^{p-1}\dots x_{k-2}^{p-1}$ equals 0. Denote $F=g(x_0,\dots,x_{k-2})+x_{k-1}h(x_0,\dots,x_{k-2})$ and write $y=(x_0,\dots,x_{k-2})$. We have $g(0)=0$, $g(y)\ne 0$ for $y\ne 0$, $h(0)\ne 0$, $h(y)=0$ for $y\ne 0$ (else we may set $x_{k-1}=-g(y)/h(y)$ and find another root of $F$.) But then we may reconstruct the coefficient of $x_0^{p-1}\dots x_{k-2}^{p-1}$ in the polynomial $h(x_0,\dots,x_{k-2})$, and it is non-zero: the sum contains unique non-negative summand (I guess, it is a partial case of Alon-Füredi theorem). A contradiction.

Your construction is optimal, that is, the degree of $f$ is always at least $2p^{k-1}-1$. Note that if $m,x$ have $p$-base expansions $m=\sum_{i}m_i p^i$, $x=\sum_{i}x_i p^i$, we have $\binom{x}{m}\equiv \prod \binom{x_i}{m_i} \pmod p$ by Lucas' theorem, and any integer-valued polynomial is an integer linear combinations of binomials $\binom{x}{m}$ (whose result is it, by the way?). So your question is essentially about polynomials in $k$ variables $x_0,\dots,x_{k-1}$ over $\mathbb{F}_p$, which are reduced (have degree at most $p-1$ in each variable). Assume that degree of $f$ is strictly less than $2p^{k-1}-1$. It means that the corresponding polynomial $F\in \mathbb{F}_p[x_0,\dots,x_{k-1}]$ is at most linear in $x_{k-1}$ and its coefficient of $x_{k-1}x_0^{p-1}\dots x_{k-2}^{p-1}$ equals 0. Denote $F=g(x_0,\dots,x_{k-2})+x_{k-1}h(x_0,\dots,x_{k-2})$ and write $y=(x_0,\dots,x_{k-2})$. We have $g(0)=0$, $g(y)\ne 0$ for $y\ne 0$, $h(0)\ne 0$, $h(y)=0$ for $y\ne 0$ (else we may set $x_{k-1}=-g(y)/h(y)$ and find another root of $F$.) But then we may reconstruct the coefficient of $x_0^{p-1}\dots x_{k-2}^{p-1}$ in the polynomial $h(x_0,\dots,x_{k-2})$, and it is non-zero: the sum contains unique non-negative summand (I guess, it is a partial case of Alon-Füredi theorem). A contradiction.