What is the reason for this apparent paradox caused by a massless spring with a locking mechanism?
If the spring locks when the ball is at rest in the lab frame, then by the arguments you give it follows that the spring must not be compressed at all. This is indeed the case.
As the ball slows down, the block begins to speed up. Eventually they are traveling at the same speed, at which point the spring has reached its maximum compression. As the spring begins to expand, the block's velocity becomes greater than that of the ball. When the spring attains its uncompressed length, the ball comes to rest and the block is traveling with speed $v$.
This can be shown directly. Let $x(t)$ be the position of the ball and $y(t)$ be the position of the block, and let us consider left to be the positive direction in accordance with your figure. At time $t=0$ the ball makes contact with the spring. Let the initial position and velocity of the ball be $x(0)=0$ and $x'(0) = v$, and the initial position and velocity of the block be $y(0)=L$ and $y'(0) = 0$ where $L$ is the (unimportant) unstretched length of the spring.
The dynamics of the system are governed by the equations
$$m x'' = k(y-x-L)$$ $$m y'' = -k(y-x-L)$$
We can define the auxiliary variables $u = \frac{x+y}{2}$ and $w = \frac{x-y+L}{2}$ to obtain $$ u'' = 0 \implies u(t)= \frac{L+vt}{2}$$ $$w'' = -\frac{k}{m} w \implies w(t)= \frac{v}{2\omega}\sin(\omega t)$$ where $\omega=\sqrt{k/m}$ and I've applied the initial conditions stated above. We can invert these relations to find $x$ and $y$ to be $$x(t) = u+w-\frac{L}{2} = \frac{vt}{2}+\frac{v}{2\omega}\sin(\omega t)$$ $$y(t) = u-w+\frac{L}{2} = L + \frac{vt}{2} - \frac{v}{2\omega}\sin(\omega t)$$
The ball comes to rest when $x'(t) = \frac{v}{2}(1+\cos(\omega t)) = 0 \implies \omega t = \pi$. However, at this time we have that $y-x = L$ and $y'= v$.
An alternative is that the spring locks when the maximum compression is achieved, i.e. when $y'=x'$. This occurs when $\cos(\omega t)=0 \implies \omega t = \pi/2$. At this moment, the velocity of the ball and the block are both $v/2$, in accordance with the conservation of momentum in a completely inelastic collision.
If the spring locks when the deformation is maximum the collision is not ellastic. At that point the relative velocity of the two objects is zero so they continue to move with the same velocity. This is a model of non-elastic collision. The collisions are ellastic when the spring does not lock and restore its potential energy into kinetic. For actual balls the spring is played by the ellasticity of the material.
The problem is exactly how billiard balls work (in 1 dimension, it's a much easier game like that). The spring is replaced by the elasticity of the ball, which doesn't need to lock, because that's how billiards works: all the cue ball's E and p go to the target ball, leaving the cue ball at rest.