We want to show
$$\text{Tr}_2\left( U_s(|q\rangle\langle q| \otimes|x^{k}\rangle \langle x^{k}| \otimes \sigma) U_s^\dagger \right) = U_k(|q\rangle\langle q|\otimes \sigma)U_k^\dagger+O(\Delta t^2)\tag{1}$$
Starting from the definition
$$
U_k = |0\rangle \langle 0| \otimes \mathbb{I} + |1\rangle \langle 1| \otimes e^{-i \Delta t|x^k\rangle \langle x^k|} \tag{2}
$$
we can evaluate the right hand side of Equation (1) as
\begin{align}
U_k(|q\rangle\langle q|&\otimes \sigma)U_k^\dagger \\
=&\left(|0\rangle \langle 0| \otimes \mathbb{I}\right)(|q\rangle\langle q|\otimes \sigma) \left(|0\rangle \langle 0| \otimes \mathbb{I}\right)\\
\quad+ &\left(|0\rangle \langle 0| \otimes \mathbb{I}\right)(|q\rangle\langle q|\otimes \sigma)\left(|1\rangle \langle 1| \otimes e^{i \Delta t|x^k\rangle \langle x^k|} \right)\\
\quad+&\left(|1\rangle \langle 1| \otimes e^{-i \Delta t|x^k\rangle \langle x^k|} \right)(|q\rangle\langle q|\otimes \sigma) \left(|0\rangle \langle 0| \otimes \mathbb{I}\right)\\
\quad+ &\left(|1\rangle \langle 1| \otimes e^{-i \Delta t|x^k\rangle \langle x^k|} \right)(|q\rangle\langle q|\otimes \sigma)\left(|1\rangle \langle 1| \otimes e^{i \Delta t|x^k\rangle \langle x^k|} \right)\\
= &|\langle 0|q\rangle|^2\left(|0\rangle \langle 0| \otimes \sigma\right)\tag{a} \\
\quad+ &\langle 0 | q \rangle \langle q | 1 \rangle |0 \rangle \langle 1| \otimes \sigma e^{i \Delta t|x^k\rangle \langle x^k|}\tag{b}\\
\quad+ &\langle 1 | q \rangle \langle q | 0 \rangle |1 \rangle \langle 0| \otimes e^{-i \Delta t|x^k\rangle \langle x^k|} \sigma \tag{c}\\
\quad+ &|\langle 1 | q \rangle |^2 |1 \rangle \langle 1 | \otimes e^{-i \Delta t|x^k\rangle \langle x^k|}\sigma e^{i \Delta t|x^k\rangle \langle x^k|} \tag{d}
\end{align}
For the left-hand side of Equation (1) , we have the definition
$$
U_s = |0 \rangle \langle 0| \otimes \mathbb{I} + |1 \rangle \langle 1 | \otimes e^{-i \Delta t S} \tag{3}
$$
With a bit of manipulation we can write the left hand side of the desired equality as
\begin{align}
\text{Tr}_2&\left(U_s(|q\rangle\langle q| \otimes |x^{k}\rangle \langle x^{k}| \otimes \sigma) U_s^\dagger \right) \\
\quad=&|\langle 0|q\rangle|^2 \text{Tr}_2\left(|0\rangle \langle 0| \otimes|x^{k}\rangle \langle x^{k}| \otimes \sigma\right)\tag{i} \\
\quad+ &\langle 0 | q \rangle \langle q | 1 \rangle \text{Tr}_2\left(|0 \rangle \langle 1| \otimes (|x^{k}\rangle \langle x^{k}| \otimes \sigma) e^{i \Delta t S}\right)\tag{ii} \\
\quad+ &\langle 1 | q \rangle \langle q | 0 \rangle \text{Tr}_2\left(|1 \rangle \langle 0| \otimes e^{-i \Delta t S}(|x^{k}\rangle \langle x^{k}| \otimes \sigma)\right) \tag{iii} \\
\quad+ &|\langle 1 | q \rangle |^2 \text{Tr}_2\left(|1 \rangle \langle 1 | \otimes e^{-i \Delta t S}(|x^{k}\rangle \langle x^{k}| \otimes \sigma) e^{i \Delta t S} \right)\tag{iv}
\end{align}
Note that each the expressions in lines (a)-(d) are mutually orthogonal to eachother based on the operator contained in the first register, and the same is true for lines (i)-(iv). So we can only recover the desired equality if line (a) is equal to line (i), and line (b) is equal to line (ii), and so on. Clearly we have (a) = (i), so we need to show (b) = (ii) and (d) = (iv), but only up to $O(\Delta t^2)$.
We can derive the following (for example, see this question):
\begin{align}
\text{Tr}_1 ((\rho \otimes \sigma) S) &= \sigma \rho \tag{4} \\
\text{Tr}_1 (S(\rho \otimes \sigma) ) &= \rho\sigma \tag{5} \\
\exp (i \Delta t S) &= \cos (\Delta t) \mathbb{I} + i \sin (\Delta t )S \tag{6}
\end{align}
where the partial trace is removing the register containing $\rho$. With this identity, the rest is just brute force and discarding higher order terms (you might want to try it again yourself before moving on!).
(b) = (ii)
Ignoring the first register we simplify Line (ii) using the formula in Equation (6):
\begin{align}
\text{Tr}_1\left((|x^{k}\rangle \langle x^{k}| \otimes \sigma) e^{i \Delta t S}\right) &=
\cos (\Delta t) \text{Tr}_1\left(|x^{k}\rangle \langle x^{k}| \otimes \sigma \right) + i \sin (\Delta t) \text{Tr}_1\left((|x^{k}\rangle \langle x^{k}| \otimes \sigma) S \right) \tag{7}\\
&=(1 - \frac{\Delta t^2}{2!} + \cdots) \sigma + i (\Delta t - \frac{\Delta t^3}{3!} + \cdots) \sigma |x^{k}\rangle \langle x^{k}| \tag{8}\\
&= \sigma \left(\mathbb{I} + i \Delta t |x^{k}\rangle \langle x^{k}|\right) + O(\Delta t ^2) \tag{9}
\end{align}
where we have used Taylor series expansions for the trigonometic functions and discarded terms of higher order in $\Delta t$. Compare this to (b) where the state in registers 2 and 3 can be rewritten using a power series for matrix exponentials as
\begin{align}
\sigma e^{i \Delta t|x^k\rangle \langle x^k|} = \sigma \left(\mathbb{I} + i \Delta t |x^{k}\rangle \langle x^{k}|\right) + O(\Delta t ^2) \tag{10}
\end{align}
and so substituting Equations (9)-(10) back into lines (ii) and (b) we have (b) = (ii) up to terms that are $O(\Delta t^2)$. This implies (c) = (iii) up to $O(\Delta t^2)$ if we just take the adjoint of both sides.
(d) = (iv)
Moving on to line (d), this can also approximated to first order in $\Delta t$ by expanding the exponential as a power series (there is also a Baker Campbell Hausdorf formula for this):
\begin{align}
e^{-i \Delta t|x^k\rangle \langle x^k|}\sigma e^{i \Delta t|x^k\rangle \langle x^k|} &= (\mathbb{I} - i \Delta t |x^k\rangle \langle x^k| + \cdots ) \sigma (\mathbb{I} + i \Delta t |x^k\rangle \langle x^k| + \cdots ) \tag{11}\\
&= \sigma + i \Delta t [\sigma, |x^k\rangle \langle x^k|] + O(\Delta t^2)\tag{12}
\end{align}
Similarly simplifying registers 2 and 3 of (iv) and liberally discarding terms of higher order gives
\begin{align}
\text{Tr}_1\left(e^{-i \Delta t S}\sigma e^{i \Delta t S} \right) &= \text{Tr}_1\left((\mathbb{I} -i \Delta t S + \cdots)(|x^{k}\rangle \langle x^{k}| \otimes \sigma) (\mathbb{I} +i \Delta t S + \cdots) \right) \tag{13}\\
&=\sigma + i \Delta t \text{Tr}_1\left((|x^{k}\rangle \langle x^{k}| \otimes \sigma) S \right) -i \Delta t
\text{Tr}_1\left(S (|x^{k}\rangle \langle x^{k}| \otimes \sigma) \right)
+ O(\Delta t^2)\tag{14} \\
&= \sigma + i \Delta t [\sigma, |x^k\rangle \langle x^k|] + O(\Delta t^2) \tag{15}
\end{align}
and so substituting Equations (12) and (15) into (d) and (iv) respectively we find (d) = (iv).
Ignoring higher order terms, we have now shown that every term on each side of Equation (1) is equal to some other term on the other side, and so Equation (1) holds.
