Why is dependence on derivatives not a problem in the definition of canonical energy-momentum tensor? Let $\mathcal L(\phi,\partial\phi)$ be a Lagrangian for a field $\phi$. It is known that the Lagrangian $\mathcal L$ and the Lagrangian $\mathcal L+\partial_\mu K^\mu$ produces the same physics, provided that $K$ depends on spacetime points through $\phi$ and $x$ only (eg. not through $\partial\phi$).
This can be seen because if the divergence term is varied, we get $$ \int_{\partial\mathcal D}d\sigma_\mu\delta K^\mu=\int_{\partial\mathcal D}d\sigma_\mu\left(\frac{\partial K^\mu}{\partial\phi}\delta\phi+\frac{\partial K^\mu}{\partial\phi_{,\mu}}\delta\phi_{,\mu}\right), $$ where I have assumed that $K$ also depends on $\phi_{,\mu}$. If only the first term was present in the brackets, then because $\delta\phi|_{\partial\mathcal D}=0$, the variation of this term would vanish. However because of the term proportional to $\delta\phi_{,\mu}$, this is no longer true.
On the other hand, if we consider invariance of a Lagrangian under spacetime-translations, because the Lagrangian is a scalar (at least in SR), under the transformation $x^\mu\mapsto x^\mu+\epsilon a^\mu$ it gets varied to $$ \delta \mathcal L=a^\mu\partial_\mu\mathcal L=\partial_\mu(a^\mu\mathcal L). $$ So in this case, $$ K^\mu=a^\mu\mathcal L, $$ but $\mathcal L$ depends on $\partial\phi$, so by the things said in the first part of this post, this is not a good $K^\mu$.
How to resolve this?
EDIT: Upon rereading my post, I realize I have been a bit too brief. To contextualize this better, a variation is a symmetry of the action if the Lagrangian gets varied to $\delta\mathcal L=\partial_\mu K^\mu$. This is a symmetry because of what I said in the first part.
This is utilized in the derivation of the canonical SEM tensor, as translations provide a symmetry of the Lagrangian because it gets varied to $\partial_\mu (a^\mu\mathcal L)$.
 A: I restrict attention on the proof of the fact that $\phi(x)$ and $\phi(x+a)$ are simultaneously solutions of E.L. equations of ${\cal L}(\phi, \partial \phi)$. I.e., spacetime displacements are (dynamical) symmetries for ${\cal L}(\phi, \partial \phi)$. Otherwise the question is too vague. 
I think this is not the right way to tackle the problem. You don't use in your attempt of proof the crucial hypothesis: 
$\qquad \qquad \qquad \qquad \qquad$ ${\cal L}$ does not depend explicitly on $x$. 
Without this fact it is false that the solutions of E-L equations  (i.e. the stationary points of the action with standard boundary conditions) are preserved under spacetime translations.  
The condition  $${\cal L}'(x,\phi(x), \partial \phi(x))= {\cal L}(x,\phi(x), \partial \phi(x))+ \partial_\mu K^{\mu}(x,\phi(x))\tag{1}$$  is just sufficient to produce the same field equations for ${\cal L}$ and ${\cal L}'$. But it is not necessary.
Furthermore it works also if an explicit dependence on $x$ shows up, whereas the absence of $x$ is crucial here. 
All that suggests that using (1) is not a good idea to prove that $\phi(x+ a)$ satisfies the same E.L. equations generated by  $${\cal L}(\phi(x), \partial \phi(x))\quad \mbox{ (I stress that no explicit dependence on $x$ appears)}$$ if $\phi(x)$ does.
Instead, a proof of this fact entirely relies on 
(i) $\frac{\partial}{\partial x^\mu} = \frac{\partial}{\partial (x+ a)^\mu}$ 
and
(ii) ${\cal L}$ does not explicitly depend on $x$.
Using them, it is easy to prove that $$\left.\left(\frac{\partial {\cal L}}{\partial \phi} - \frac{\partial}{\partial x^\mu}\frac{\partial {\cal L}}{\partial \partial_\mu \phi}\right)\right|_{\phi(x+a)} = \left.\left[\left.\left(\frac{\partial {\cal L}}{\partial \phi} - \frac{\partial}{\partial x^\mu}\frac{\partial {\cal L}}{\partial \partial_\mu \phi}\right)\right|_{\phi(z)}\right]\right|_{z=x+a}$$
The right-hand side vanishes for every value of $z$ by hypothesis so that 
$$\left.\left(\frac{\partial {\cal L}}{\partial \phi} - \frac{\partial}{\partial x^\mu}\frac{\partial {\cal L}}{\partial \partial_\mu \phi}\right)\right|_{\phi(x+a)} = 0\:.$$
A: *

*At the heart of OP's question (v2) seems to be the fact that for a quasisymmetry
$$\delta S ~\sim~ \int_V \mathrm{d}^nx~d_{\mu}k^{\mu}, $$ 
the $k^{\mu}$ functions are allowed to (and typically do) depend on derivatives of the fields $\phi$ without spoiling the conclusions of Noether's (first) theorem.

*The Lagrangian density could in principle depend on higher derivatives, although there could be a price to pay, cf. e.g. this and this Phys.SE posts.

*Adding total divergence terms to the Lagrangian density is also discussed in this Phys.SE post and links therein.

*Specifically OP considers spacetime translation symmetry, i.e. energy-momentum conservation. This is e.g. discussed in this Phys.SE post and links therein.
A: I think @Qmechanic 's answer is great because it brings a lot of interesting topics to the table. Let me just add this.
Take this example: $L=\partial_\mu \phi \partial^{\mu} \phi $. Let's apply a finite translation: $x\rightarrow x-a$. The Lagrangian becomes $L \rightarrow L'= \partial_\mu \phi' \partial^{\mu} \phi' $ with $\phi'=\phi'(z)=\phi(x+a)$, $z=x+a$. You are free to write this as $L'= \partial'_\mu \phi' \partial'^{\mu} \phi'$ with $\partial'_\mu=\frac{\partial}{\partial z^\mu}$. Then, if we variate with respect to $\phi'$, we will reproduce the same equations of motion. But notice that from the point of view of the original field $\phi(x)$, this transformed Lagrangian $L'$ depends on all of its derivatives, since $\phi'=\phi(x+a)=\sum^{\infty}_{k=0} \frac{1}{k!} a^{k} \partial_{k} \phi(x)$.
As you mention, an infinitesimal transformation will generically insert higher order derivatives. Generically we can't expect this transformed quantity to vanish on-shell without the need for additional artifices/boundary conditions, as it was pointed out in the other answer and this should not surprise us. And, as this example points out, once we perform a symmetry transformation, there is no point in using the original fields (evaluated in the same position) to variate the action. 
