The simplest (minimally measure-theoretic) approach that I found is the following:
First, define a history of the states in all periods except for periods $k$, $n$ and $n+1$ as follows
$ H = \Big\{ X_1(\omega_1) = x_1, \ldots, X_{k-1}(\omega_{k-1}) = x_{k-1}, X_{k+1}(\omega_{k+1}) = x_{k+1}, \ldots X_{n-1}(\omega_{n-1}) = x_{n-1} \ \Big| \ \omega_1 \in \Omega_{1},\omega_{k-1} \in \Omega_{k-1},\omega_{k+1} \in \Omega_{k+1},\omega_{n-1} \in \Omega_{n-1} \Big \} $
where $h$ denote a particular realization of $H$.
Using, this we can see that:
$\begin{align} \mathbb{P}(X_{n+1} = x_{n+1} | X_n = x_n, X_k = x_k ) &= \sum_{h \in H} \mathbb{P}(X_{n+1} = x_{n+1}, \ h \ | \ X_n = x_n, X_k = x_k) \\ &= \sum_{h \in H} \mathbb{P}(X_{n+1} = x_{n+1} \ | \ h, X_n = x_n, X_k = x_k) \mathbb{P}(h \ | \ X_n = x_n, X_k = x_k) \\ \end{align}$
Now we note that:
$\begin{align} \mathbb{P}(X_{n+1} = x_{n+1} \ | \ h, X_n = x_n, X_k = x_k) &= \mathbb{P}( X_{n+1} = x_{n+1} \ | \ X_n = x_n, X_{n-1} = x_{n-1},\ldots, X_1 = x_1 ) \\ &= \mathbb{P}( X_{n+1} = x_{n+1} \ | \ X_n = x_n) \end{align}$
by the definition of $h$ and the Markov Property.
Similarly,
$ \begin{align} \mathbb{P}(h \ | \ X_n = x_n, X_k = x_k) &= \mathbb{P}( X_{n-1} = x_{n-1}, \ldots, X_{k+1} = x_{k+1}, X_{k-1} = x_{k-1}, \ldots, X_1 \ | \ X_n = x_n, X_k = x_k ) \\ &= \mathbb{P}( X_{n-1} = x_{n-1}, \ldots, X_{k+1} = x_{k+1}, X_{k-1} = x_{k-1}, \ldots, X_1 ) \\ & = \mathbb{P}(h) \end{align}$
Substituting these expressions in, we get that:
$\begin{align} \mathbb{P}(X_{n+1} = x_{n+1} | X_n = x_n, X_k = x_k ) &= \sum_{h \in H} \mathbb{P}(X_{n+1} = x_{n+1} \ | \ h, X_n = x_n, X_k = x_k) \mathbb{P}(h \ | \ X_n = x_n, X_k = x_k) \\ &= \mathbb{P}(X_{n+1} = x_{n+1} \ | X_n = x_n) \sum_{h \in H} \mathbb{P}(h) \\ &= \mathbb{P}(X_{n+1} = x_{n+1} \ | X_n = x_n) \\ \end{align}$
which proves the desired result.