I don't have a copy of Srednicki's text on hand, so I'll start by transcribing the question into equations so the OP can check whether or not I'm interpreting the question correctly.
The current $j^\mu\propto\overline\psi\gamma^\mu\psi$ satisfies $\partial_\mu j^\mu=0$ whenever $\psi$ satisfies the equation of motion $(i\gamma^\mu D_\mu+m)\psi=0$ with $D_\mu=\partial_\mu-iA_\mu$, even though $\partial_\mu j^\mu\neq 0$ for most $\psi$. In other words, the current is only conserved "on-shell."
The current $j^\mu$ in $\partial_\nu F^{\nu\mu}\propto j^\mu$ must satisfy $\partial_\mu j^\mu=0$ identically, because $\partial_\mu\partial_\nu F^{\nu\mu}=0$ identicaly due to the antisymmetry of $F^{\mu\nu}$, without the help of any independent equation of motion for $j^\mu$. In other words, the current is conserved "off-shell."
In QED, the equations of motion $(i\gamma^\mu D_\mu+m)\psi=0$ and $\partial_\nu F^{\nu\mu}\propto j^\mu$ (with $j^\mu\propto\overline\psi\gamma^\mu\psi$) both follow from the same Lagrangian.
The wording in point 2 might be a little misleading (both here and in the OP), because the "off-shell" conservation law for $j^\mu$ in point 2 exploits the fact that the gauge field $A_\mu$ is on-shell, because we used its equation of motion.
With that in mind, the logic leading from 4 to 5 could be re-worded in terms of the idea that the equation of motion for the gauge field somehow implies something about the behavior of the Dirac field. It doesn't imply the full equation of motion for the Dirac field, but it implies enough to enforce the conservation law.
The key is the fact that in the QED action $S=S_A+S_\psi$, where $S_A$ is the part involving only the gauge field and where $S_\psi$ includes all terms involving the Dirac field, each of these two terms is gauge-invariant by itself. This fact can be used to explain why either equation of motion by itself, the one for $\psi$ or the one for $A$, implies the conservation law $\partial_\mu j^\mu=0$.
I assume that's what Srednicki meant by the statement that the paradox is solved by appealing to gauge symmetry.
Here's the explicit logic: The fact that $S_A$ and $S_\psi$ are each invariant under the gauge transformation $A\to A+\partial\theta$ implies
$$
\frac{\delta S_A}{\delta\theta} = 0
\hskip2cm
\frac{\delta S_\psi}{\delta\theta} = 0.
\tag{1}
$$
The fact that the first of these equations holds for an arbitrary smooth function $\theta(x)$ implies
$$
\partial_\mu\frac{\delta S_A}{\delta A_\mu} = 0.
\tag{2}
$$
(To see this, use the chain rule in the first of equations (1) and then integrate-by-parts.) Equation (2) is an expression of the identity
$$
\partial_\mu\partial_\nu F^{\mu\nu}=0,
\tag{3}
$$
which we already observed implies the conservation law, because the equation of motion for $A$ is
$$
\frac{\delta S_A}{\delta A_\mu}+
\frac{\delta S_\psi}{\delta A_\mu} = 0.
\tag{4}
$$
Again, this deduces a constraint on the behavior of the Dirac field from the equation of motion for the gauge field.
The fact that the second of equations (1) holds for an arbitrary smooth function $\theta(x)$ implies
$$
\partial_\mu\frac{\delta S_\psi}{\delta A_\mu} = 0.
\tag{5}
$$
This is deduced using only use the equation of motion for the Dirac field (only $S_\psi$) and not the equation of motion for the gauge field (not $S_A$). The method of proof is similar: use the chain rule in the second of equations (1), remembering that $S_\psi$ depends on both $\psi$ and $A_\mu$.
In both cases, the derivation of the conservation law from gauge invariance (starting from either $S_A$ or $S_\psi$) uses the fact that $\theta(x)$ can be an arbitrary smooth function, because then $\int dx\ f(x)\theta(x)=0$ implies $f(x)=0$. In this sense, gauge-invariance explains why we get the same conservation law from either part of the action.
By the way, a similar line of reasoning can be used on general relativity to explain why the stress-energy conservation law $\nabla_\mu T^{\mu\nu}=0$ can be derived either from consistency with the Einstein field equation or directly from the matter-field equations of motion (where "matter" in this case may include the EM field, as noted in an earlier post by knzhou).
Also by the way, I used the name "QED" here (as in the OP), but some of the thinking is classical — namely the idea that a given field may or may not satisfy its equation of motion. (In quantum field theory, the fields always satisfy their equations of motion, because that's how we define the time-dependence of the Heisenberg field operators.)
