tl;dr: The inequality in its current form is wrong, although a weaker version of it (where the right-hand side has an additional factor of $2$) holds true.
For a counterexample to the inequality as stated—found by means of simple numerics—consider the (unital) quantum channel $\mathcal E$ defined by its Pauli transfer matrix
$$
\mathsf P(\mathcal E)=\begin{pmatrix}
1&0&0&0\\
0&3/5&0&-4/5\\
0&0&0&0\\
0&0&0&0
\end{pmatrix}\,;
$$
equivalently, its Choi matrix reads
$$
\mathsf C(\mathcal E)=\begin{pmatrix}
\frac{1}{2} & -\frac{2}{5} & 0 & \frac{3}{10} \\
-\frac{2}{5} & \frac{1}{2} & \frac{3}{10} & 0 \\
0 & \frac{3}{10} & \frac{1}{2} & \frac{2}{5} \\
\frac{3}{10} & 0 & \frac{2}{5} & \frac{1}{2}
\end{pmatrix}
$$
so $\mathcal E$ is completely positive as $\mathsf C(\mathcal E)$ has eigenvalues $1$ (2-fold) and $0$ (2-fold). Next consider the (pure) states
\begin{align*}
\rho=\begin{pmatrix}
\frac14&\frac{\sqrt3}4\\
\frac{\sqrt3}4&\frac34
\end{pmatrix}\qquad\text{ and }\qquad\sigma=
\begin{pmatrix}
1&0\\0&0
\end{pmatrix}
\end{align*}
so
\begin{align*}
\|\mathcal E(\rho-\sigma)\|_1&= \Big\|\mathcal E\begin{pmatrix}
-\frac34&\frac{\sqrt3}4\\
\frac{\sqrt3}4&\frac34
\end{pmatrix} \Big\|_1\\
&= \Big\|\Big(\frac{3 \sqrt{3}}{20}+\frac35\Big)\sigma_x\Big\|_1=\frac{3 \sqrt{3}}{10}+\frac{6}{5}\approx 1.71962\,.
\end{align*}
On the other hand using the matrix form of the CNOT we compute
\begin{align*}
\|(\mathcal{E}\otimes\,&{\rm id})(U((\rho - \sigma)\otimes |0\rangle\langle 0|)U^{\dagger})\|_1\\
&=\Big\|(\mathcal{E}\otimes{\rm id})\Big(\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}
\begin{pmatrix} -\frac34&0&\frac{\sqrt3}4&0\\
0&0&0&0\\
\frac{\sqrt3}4&0&\frac34&0\\
0&0&0&0\end{pmatrix}
\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}\Big)\Big\|_1\\
&=\Big\|(\mathcal{E}\otimes{\rm id})
\begin{pmatrix} -\frac34&0&0&\frac{\sqrt3}4\\
0&0&0&0\\
0&0&0&0\\
\frac{\sqrt3}4&0&0&\frac34\end{pmatrix}
\Big\|_1\\
&=\Big\|\begin{pmatrix}
-\frac{3}{8} & 0 & \frac{3}{10} & \frac{3 \sqrt{3}}{40} \\
0 & \frac{3}{8} & \frac{3 \sqrt{3}}{40} & \frac{3}{10} \\
\frac{3}{10} & \frac{3 \sqrt{3}}{40} & -\frac{3}{8} & 0 \\
\frac{3 \sqrt{3}}{40} & \frac{3}{10} & 0 & \frac{3}{8}
\end{pmatrix}\Big\|_1\\
&=\frac{3\sqrt7}5\approx1.58745
\end{align*}
which is strictly smaller than $\|\mathcal E(\rho-\sigma)\|_1\approx 1.71962$, a contradiction.
Now for the promised weaker bound:
for all linear maps $\mathcal E:\mathbb C^{2\times 2}\to\mathbb C^{2\times 2}$ and all $X\in\mathbb C^{2\times 2}$ it holds that
$$
\boxed{\|\mathcal E(X)\|_1\leq2\|(\mathcal{E}\otimes{\rm id})(U(X\otimes |0\rangle\langle 0|)U^{\dagger})\|_1}\,.\tag0
$$
In particular this holds when $\mathcal E$ is CPTP and $X=\rho-\sigma$ is the difference of any two states.
This is a direct consequence of the following identity:$$
{\rm tr}_{2,|{\bf e}\rangle\langle{\bf e}|}\big((\mathcal E\otimes{\rm id})(U(X\otimes |0\rangle\langle 0|)U^\dagger)\big)=\mathcal E(X)\tag1
$$
where $|{\bf e}\rangle:=|0\rangle+|1\rangle$ and ${\rm tr}_{2,Y}$ for any $Y$ is defined via ${\rm tr}_{2,Y}(A\otimes B):=A\,{\rm tr}(BY)$ for all $A,B$.
Proof of Eq.(1). Using $U=|0\rangle\langle 0|\otimes{\bf1}+|1\rangle\langle 1|\otimes\sigma_x$ we compute
\begin{align*}
&{\rm tr}_{2,|{\bf e}\rangle\langle{\bf e}|}\big((\mathcal E\otimes{\rm id})(U(X\otimes |0\rangle\langle 0|)U^\dagger)\big)\\
&= {\rm tr}_{2,|{\bf e}\rangle\langle{\bf e}|}\big((\mathcal E\otimes{\rm id})(|0\rangle\langle 0|X|0\rangle\langle 0|\otimes |0\rangle\langle 0|+
|0\rangle\langle 0|X|1\rangle\langle 1|\otimes |0\rangle\langle 1|\\
&\qquad+|1\rangle\langle 1|X|0\rangle\langle 0|\otimes |1\rangle\langle 0|+
|1\rangle\langle 1|X|1\rangle\langle 1|\otimes |1\rangle\langle 1|)U^\dagger)\big) \\
&=\langle 0|X|0\rangle {\rm tr}_{2,|{\bf e}\rangle\langle{\bf e}|}\big(\mathcal E(|0\rangle\langle 0|)\otimes|0\rangle\langle 0|\big) +\langle 0|X|1\rangle {\rm tr}_{2,|{\bf e}\rangle\langle{\bf e}|}\big(\mathcal E(|0\rangle\langle 1|)\otimes|0\rangle\langle 1|\big)\\
&\qquad +\langle 1|X|0\rangle {\rm tr}_{2,|{\bf e}\rangle\langle{\bf e}|}\big(\mathcal E(|1\rangle\langle 0|)\otimes|1\rangle\langle 0|\big) +\langle 1|X|1\rangle {\rm tr}_{2,|{\bf e}\rangle\langle{\bf e}|}\big(\mathcal E(|1\rangle\langle 1|)\otimes|1\rangle\langle 1|\big)\\
&=\langle 0|X|0\rangle\mathcal E(|0\rangle\langle 0|)\langle{\bf e}|0\rangle\langle 0|{\bf e}\rangle+\langle 0|X|1\rangle\mathcal E(|0\rangle\langle 1|)\langle{\bf e}|0\rangle\langle 1|{\bf e}\rangle\\
&\qquad \langle 1|X|0\rangle\mathcal E(|1\rangle\langle 0|)\langle{\bf e}|1\rangle\langle 0|{\bf e}\rangle+\langle 1|X|1\rangle\mathcal E(|1\rangle\langle 1|)\langle{\bf e}|1\rangle\langle 1|{\bf e}\rangle\\
&=\mathcal E\big(
|0 \rangle\langle 0|X|0 \rangle\langle0 |+
|0 \rangle\langle 0|X|1 \rangle\langle1 |+
|1 \rangle\langle 1|X|0 \rangle\langle0 |+
|1 \rangle\langle 1|X|1 \rangle\langle1 | \big)=\mathcal E(X)\tag*{$\square$}
\end{align*}
From (1) it immediately follows that
\begin{align*}
\|\mathcal E(X)\|_1&=\big\|{\rm tr}_{2,|{\bf e}\rangle\langle{\bf e}|}\big((\mathcal E\otimes{\rm id})(U(X\otimes |0\rangle\langle 0|)U^\dagger)\big)\big\|_1\\
&\leq\|{\rm tr}_{2,|{\bf e}\rangle\langle{\bf e}|}\|_{1\to1}\big\|(\mathcal E\otimes{\rm id})(U(X\otimes |0\rangle\langle 0|)U^\dagger)\big\|_1
\end{align*}
This would imply (0) once we can show that $\|{\rm tr}_{2,|{\bf e}\rangle\langle{\bf e}|}\|_{1\to1}=2$. Indeed, imitating the standard computation that the usual partial trace is trace-norm contractive this follows from the fact that the adjoint channel of ${\rm tr}_{2,|{\bf e}\rangle\langle{\bf e}|}$ is $X\mapsto X\otimes|{\bf e}\rangle\langle{\bf e}|$ together with the readily verified fact that $\||{\bf e}\rangle\langle{\bf e}|\|_\infty=\|{\bf e}\|^2=\langle{\bf e}|{\bf e}\rangle=2$.
