For $N = 2$, I think the (likely obvious) strategy of "always guess different" is optimal, giving expected hitting time $K^2$. I think we can show this using dynamic programming using the potential function (edit: added simpler equivalent expression)
$$\begin{aligned}
\Phi(x_1, x_2)
&= (K - x_1)(K - x_2) \\ &= \biggl(K - \frac{x_1 + x_2}{2}\biggr)^2 - \biggl(\frac{x_1 - x_2}{2}\biggr)^2.
\end{aligned}$$
However, I'm neglecting details to do with unboundedness of the state space. Posting what I have in case someone can add the missing piece, or in case the intuition helps when extending to $N \geq 3$.
We satisfy the necessary boundary condition: $\Phi(K, x_2) = \Phi(x_1, K) = 0$. If the state space were bounded, it would suffice to show we satisfy the Bellman equation when $\max\{x_1, x_2\} < K$. (The state space is unbounded, but let's keep going anyway.)
Let $R \sim \operatorname{Rademacher}$ (i.e. a $\pm 1$ coin flip). The expected change in $\Phi$ under each action is
$$\begin{aligned}
\Delta_{\text{different}} \Phi(x_1, x_2)
&:= \mathbb{E}[\Phi(x_1 + R, x_2 - R) - \Phi(x_1, x_2)]
= -1,
\\
\Delta_{\text{same}} \Phi(x_1, x_2)
&:= \mathbb{E}[\Phi(x_1 + R, x_2 + R) - \Phi(x_1, x_2)]
= +1.
\end{aligned}$$
(One way to do these computations easily is to notice that "different" changes the difference $x_1 - x_2$ by $\pm 2$ while keeping the sum $x_1 + x_2$ the same, and vice versa for "same".)
Because each step incurs cost $1$, the Bellman equation we hope to satisfy is
$$
\min\{\Delta_{\text{different}} \Phi(x_1, x_2), \Delta_{\text{same}} \Phi(x_1, x_2)\} = -1,
$$
with the minimizing operator corresponding to the optimal action. And indeed, this holds, and "different" is always the optimal action.
