Why can we shift the field $\phi$, so that $\langle \Omega | \phi(x) | \Omega \rangle = 0$?

I think you just misunderstood the claim of "this does not affect the physics". If shifting the field so that its VEV is zero causes linear (or other) terms in the Lagrangian, then we must deal with these additional terms - they are a feature of the theory, but in order to apply LSZ we still need to deal with the theory in terms of the field that has zero VEV.

No one claims that that the Lagrangian is invariant under the shift operation, just that the shift operation is allowed. To make an analogy, this is equivalent to the claim that e.g. a shift of the origin in classical point mechanics "does not affect the physics". Of course, unless the system is translation-invariant, this does change the form of the action. But it does not change the physics, the system is still the same, just expressed in different coordinates.

First of all, kudos for a well-researched opening post.

1. Lorentz covariance implies that $\langle \Omega | \phi^k | \Omega\rangle=\langle \phi^k \rangle_{J=0}$ vanish for non-scalar fields, so let's assume that $\phi^k$ are scalar fields.

2. A field redefinition $\phi^k= \bar{\phi}^k + c^k$ is just a change of coordinates, which is always possible and doesn't change the path integral, cf. the other answers.

3. The form of the Lagrangian density inside of the action $\bar{S}[\bar{\phi}]:= S[\phi]=S[\bar{\phi} + c]$ would in general change accordingly. The shift would trickle down from higher-order terms to lower-order terms.

   In particular, if before the field redefinition ${\cal L}_1= Y_k\phi^k$ denotes the terms linear in the field, then after the field redefinition, the terms linear in the field would be $\bar{\cal L}_1= \bar{Y}_k\bar{\phi}^k$ for some (in general new) coefficient $\bar{Y}_k$.

   (The $Y_k$ notation is inspired by Ref. 1. Note that the $Y_k\phi^k$ term looks similar to an external source term $J_k\phi^k$. The difference is that the $Y_k$ are assumed to be intrinsic to the model.)

4. A non-zero $\langle \Omega | \phi^k | \Omega\rangle$ reflects transitions between the vacuum and 1-particle states, cf. e.g. this Phys.SE post. (It should perhaps be stressed that the above field redefinition would change the definition of 1-particle states, but not the underlying physics, only the picture.)

5. One may show that the condition $\langle \phi^k \rangle_{J=0}=0$ simplifies the perturbation theory considerably, cf. a proposition in my Phys.SE answer here.

6. Alternatively, a shifting of the value of $\langle \phi^k \rangle_{J=0}$ can be related to a shifting of the $Y_k$ coefficients in the action: To the zeroth order ${\cal O}(g^0)$ in the coupling constants $g$ (or equivalently, if we turn off interactions $g=0$), then the condition $\langle \phi^k \rangle_{J=0}=0$ is equivalent to that $Y_k={\cal O}(g^1)$ vanish.

   Conversely, in order to fulfill $\langle \phi^k \rangle_{J=0}=0$ to all orders in perturbation theory, there must be appropriate (possibly infinite) counterterms within the $Y_k$ coefficients.

   See e.g. Ref. 1 for details.

References:

1. M. Srednicki, QFT, 2007; chapter 9. A prepublication draft PDF file is available here.