Does the change in kinetic energy of an object depend on the reference frame?

Your analysis is correct. In the case of one-dimensional motion with $0 leq |v|$ the changes in kinetic energy of a particle traveling at speeds $V_1$ and $V_2$ w.r.t. the reference frame $S$ w.r.t. which the reference frame $S*$ travels at velocity $v$. The changes are $Delta K_S = frac{1}{2}m(V_2^2 - V_1^2)$ and $Delta K_{S'} = frac{1}{2} m ((V_2 - v)^2 - (V_1 - v)^2)$ with $Delta K_S = Delta K_{S'}$ if and only if $V_1 = V_2$ or $v = 0$, that is the trivial case. In the multi-dimensional case, we can similarly obtain the analogous necessary and sufficient condition for equality in the change of kinetic energy calculated using the two different frames as $(vec{V}_1 - vec{V}_2)cdotvec{v} = 0$. In the non-trivial case, this condition essentially means that the differential $(vec{V}_1 - vec{V}_2) perp vec{v}$, that is, the differential occurs in a direction perpendicular to $vec{v}$, thus leading to the interpretation related to the one-dimensional analog.

Notice that the application of the work-energy theorem (work done by external conservative forces on a material particle $W$ equals the change in it's kinetic energy, in the absence of non-conservative forces) would also need to incorporate the change in reference frame of observation. Let us take a brief look at the case in which $S$ is an inertial reference frame, so that $S'$ is one as well because we assume that the latter moves with respect to the former with a constant velocity $vec{v}$. Abusing the notation, the work done (in the context of the analysis above) calculated using the two reference frames is then obtained as $W_S = int_1^2 vec{F}^text{ext} cdot vec{V} ; dt$ and $W_{S'} = int_1^2 vec{F}^text{ext} cdot (vec{V} - vec{v}) ; dt$. Verifying the statement of the work-energy theorem by evaluating these integrals is a good way to understand that $W_S = Delta K_S$ is in general not equal to $W_{S'} = Delta K_{S'}$, with the condition for equality being $(vec{V}_1 - vec{V}_2) perp vec{v}$.

In the case that either one or both reference frames are non-inertial, application of the work-energy theorem is more complicated than the analysis presented here.