How is it possible for the same force to do different amounts of work in two different inertial frames?

You have correctly discovered that power, work, and kinetic energy are all frame variant. This is well-known for centuries, but is always surprising to a student when they first discover it. For some reason, it is not part of a standard physics curriculum.

So, the reason that this is disturbing to every student who encounters it is that it seems irreconcilable with the conservation of energy. If the work done is different in different reference frames then how can energy be conserved in all frames?

The key is to recognize that the force doing work acts on two bodies. In this case the object and the horizontal surface. You must include both bodies to get a complete picture of the conservation of energy.

Consider the situation in your example from an arbitrary frame where the horizontal surface (hereafter the "ground") is moving at a velocity $u$, the ground frame then being the frame $u=0$. Let the ground have mass $M$. The initial kinetic energies are:

$$KE_{obj}(0)=\frac{1}{2}m (v+u)^2$$ $$KE_{gnd}(0)=\frac{1}{2} M u^2$$

Now, the friction force $-f$ acts on the object until $v_{obj}(t_f)=v_{gnd}(t_f)$. Solving for the time gives $$t_f=\frac{m M v}{(m+M) f}$$ and, by Newton's 3rd law, a force $f$ acts on the ground for the same time.

At $t_f$ the final kinetic energies are:

$$KE_{obj}(t_f)=\frac{1}{2} m \left(\frac{Mu+m(u+v)}{m+M} \right)^2$$ $$KE_{gnd}(t_f)=\frac{1}{2} M \left(\frac{Mu+m(u+v)}{m+M} \right)^2$$ so $$\Delta KE_{obj}+\Delta KE_{gnd}=-\frac{m M v^2}{2(m+M)}$$

Note importantly that the total change in KE is independent of $u$, meaning that it is frame invariant. This is the amount of energy that is converted to heat at the interface. So even though the change in KE for the object itself is frame variant, when you also include the ground then you find that the total change in kinetic energy is frame invariant which allows energy to be conserved since the amount of heat generated is frame invariant.

Forces don't operate on only one object. It's difficult to see, but the other object in the force pair here is the ground/earth.

In the frame where the ground is stationary, friction does no work on the earth, so we can discard the effects. But in a frame where the ground is moving, friction does work on it as well.

In any frame, the sum of all work done is identical, but it may be distributed between the two objects in different amounts. Perhaps in the earth stationary frame the net result is the object loses 50J and 50J of heat is produced. In a different frame you might find the object loses 250J, the earth gains 200J, and 50J of heat is produced.

The coefficient of friction is the same in both cases. You have assumed the distance traveled to be the same in both cases, which is why you are getting different values for $\alpha$. Your other questions have been cleared in many answers above, so I just wanted to mention this point.