I) Let there be given a local action functional
$$ S_V[\phi]~=~\int_V \mathrm{d}^nx ~{\cal L}, \tag{1}$$
with the Lagrangian density
$$ {\cal L}(\phi(x),\partial\phi(x),x).\tag{2} $$
[We leave it to the reader to extend to higher-derivative theories. See also e.g. Ref. 1.]
II) We want to study an infinitesimal variation$^1$
$$ \delta x^{\mu}~=~\epsilon X^{\mu} \qquad\text{and}\qquad
\delta\phi^{\alpha}~=~\epsilon Y^{\alpha}\tag{3}$$
of spacetime coordinates $x^{\mu}$ and fields $\phi^{\alpha}$, with arbitrary $x$-dependent infinitesimal $\epsilon(x)$, and with some given fixed generating functions
$$ X^{\mu}(x)\qquad\text{and}\qquad Y^{\alpha}(\phi(x),\partial\phi(x),x).\tag{4}$$
It is implicitly assumed that under a variation the integration region $V$ changes according to the vector field $X^{\mu}$. Then the corresponding infinitesimal variation of the action $S_V$ takes the form$^2$
$$ \delta S_V ~\sim~ \int_V \mathrm{d}^n x \left(\epsilon ~ k + j^{\mu} ~ d_{\mu} \epsilon \right) \tag{5}$$
for some structure functions
$$ k(\phi(x),\partial\phi(x),\partial^2\phi(x),x)\tag{6}$$
and
$$ j^\mu(\phi(x),\partial\phi(x),x).\tag{7}$$
[One may show that some terms in the $k$ structure function (6) are proportional to eoms, which are typically of second order, and therefore the $k$ structure function (6) may depend on second-order spacetime derivatives.]
III) Next we assume that the action $S_V$ has a quasisymmetry$^3$ for $x$-independent infinitesimal $\epsilon$. Then eq. (5) reduces to
$$ 0~\sim~\epsilon\int_V \mathrm{d}^n x~ k. \tag{8}$$
IV) Now let us return to OP's question. Due to the fact that eq. (8) holds for all off-shell field configurations, we may show that eq. (8) is only possible if
$$ k ~=~ d_{\mu}k^{\mu} \tag{9}$$
is a total divergence. (Here the words on-shell and off-shell refer to whether the eoms are satisfied or not.) In more detail, there are two possibilities:
If we know that eq. (8) holds for every integration region $V$, we can deduce eq. (9) by localization.
If we only know that eq. (8) holds for a single fixed integration region $V$, then the reason for eq. (9) is that the Euler-Lagrange derivatives of the functional $K[\phi]:=\int_V \mathrm{d}^n x~ k$ must be identically zero. Therefore $k$ itself must be a total divergence, due to an algebraic Poincare lemma of the so-called bi-variational complex, see e.g. Ref. 2. [Note that there could in principle be topological obstructions in field configuration space which ruin this proof of eq. (9).] See also this related Phys.SE answer by me.
V) One may show that the $j^\mu$ structure functions (7) are precisely the bare Noether currents. Next define the full Noether currents
$$ J^{\mu}~:=~j^{\mu}-k^{\mu}.\tag{10}$$
On-shell, after an integration by parts, eq. (5) becomes
$$ \begin{align} 0~\sim~~~~~&\text{(boundary terms)}~\approx~ \delta S_V \cr
~\stackrel{(5)+(9)+(10)}{\sim}&
\int_V \mathrm{d}^n x ~ J^{\mu}~ d_{\mu}\epsilon \cr
~\sim~~~~~& -\int_V \mathrm{d}^n x ~ \epsilon~ d_{\mu} J^{\mu} \end{align}\tag{11}$$
for arbitrary $x$-dependent infinitesimal $\epsilon(x)$. Equation (11) is precisely OP's sought-for eq. (*).
VI) Equation (11) implies (via the fundamental lemma of calculus of variations) the conservation law
$$ d_{\mu}J^{\mu}~\approx~0, \tag{12}$$
in agreement with Noether's theorem.
References:
P.K. Townsend, Noether theorems and higher derivatives, arXiv:1605.07128.
G. Barnich, F. Brandt and M. Henneaux, Local BRST cohomology in gauge theories, Phys. Rep. 338 (2000) 439, arXiv:hep-th/0002245.
--
$^1$ Since the $x$-dependence of $\epsilon(x)$ is supposed to be just an artificial trick imposed by us, we may assume that there do not appear any derivatives of $\epsilon(x)$ in the transformation law (3), as such terms would vanish anyway when $\epsilon$ is $x$-independent.
$^2$ Notation: The $\sim$ symbol means equality modulo boundary terms. The $\approx$ symbol means equality modulo eqs. of motion.
$^3$ A quasisymmetry of a local action $S_V=\int_V d^dx ~{\cal L}$ means that the infinitesimal change $\delta S_V\sim 0$ is a boundary term under the quasisymmetry transformation.