What you have here is two blocks: one of mass $M$ and one of mass $+\infty$ and a spring of mass $m=0.$ So you have all the fun of zero mass and on top, now you have the fun of mass $+\infty$ too.
Newton's third law always holds. However, since the action-reaction pairs always apply to two different objects and only one of your objects has finite mass you don't use it very much. Or really need to worry about it at all if people have already told you how to figure it out. But let's see what happens if you track everything.
So first let's talk about infinite mass objects; basically they move at constant velocity regardless of what force you exert. Never let them collide. Luckily, they don't exist, so don't worry about it too much.
Next let's talk about zero mass Newtonian objects; if they feel a force imbalance they can instantly move in the direction of the force regardless of their current velocity and do so to adjust their location and velocity until they feel zero force. Their velocity at that point is indeterminate; however it often ends up similar to the parts they are next to unless there are multiple ways it can move or be and have no force on it. Never confuse a massless Newtonian object with a massless Relativistic object. The former can move at any speed, or even have an indeterminate speed, the later must move at the speed of light.
Now we can talk about objects with finite mass. They accelerate according to $F=ma$.
To talk about your problem, the first step is to be more explicit about the set-up. We can put them in space or we can out them on a level frictionless surface.
So the block of mass $M$ is moving to the right. To the right is a spring at rest of length $L$ and it is attached to a block of mass $+\infty$ on its right, which is also at rest.
Up until the block of mass $M$ touches the spring, there are no forces whatsoever. So, the blocks move at a steady velocity and the spring and the heavy block stay at rest.
Then it touches.
It must exert a force to move the spring out of its way. A real block would itself be like a very stiff spring; it would compress and that compression would be how it exerts a force on the spring. But since the spring is massless no force is required to make it move & so it can effortlessly move out of the way and since it is massless it will move until it feels zero force.
So let's describe the motion of the block of mass $M$. With the origin of time being when it first touches the spring and the origin of space being where it first touches the spring we have a position as a function of time $x(t)$ and $x(t)=vt$ for some fixed $v>0$ when $t\leq 0.$
This isn't very detailed. But it does show that it moved at constant velocity back when it had no force on it. And we can compute the acceleration on it after $t=0$ too. I'll use calculus since it was invented to do these physics problems. $Mx''(t)\hat x$ equals the force on the block of mass $M$. Super. Still not very detailed.
Now let's talk about the spring. It has lots of layers. A leftmost layer, a middle layer, a right most layer, and more in between. Each layer is in the way of the one to the left so when I say it can move at any speed since it is massless what happens in this case is that it compresses. You could even give each layer a bit of mass $dm$ and then let the mass go to zero after you set up your equations. That limit, after the fact, is actually how we figure out what massless Newtonian objects do.
So it compresses, starting at time $t=0.$ Remember that it compresses until it feels zero force. Let's find out the force. At time $t$, the left block is feeling a force $Mx''(t)\hat x$ so by Newton's Third Law the spring is feeling a force due to the left block of $-Mx''(t)\hat x$ and it needs to compress until it feels zero force (because the massless parts have to move until they feel no force and because they are layers the motion is compression). So the mass compresses until the force it feels is zero and the force from the left block is $-Mx''(t)\hat x$ so it need to compress until it feels a force of $+Mx''(t)\hat x$ from the right block. And I say until, but since it is massless and Newtonian it happens instantly.
We could use Newton's Third Law again to find the force the right block feels from the spring (which is equal and opposite to the force $+Mx''(t)\hat x$ the spring feels from the right block) and the right block feels a force of $-Mx''(t).$
So, the two blocks feel equal and opposite forces and the spring feels no net force. And the spring still accelerates (compresses) even though it feels no force because it is massless. You can think of it as having a super tiny mass and so it feels a super tiny force and so the two forces on it almost perfectly balance, so it can move and we are approximating the true force which is tiny with a zero force.
And every single force seems to be related to how the block is accelerating which seems a bit circular and vague. But basically all we've said about the spring is that it can exert forces and that it has very little, or no, mass. We now need to quantify how the spring exerts forces.
So here comes Hooke's Law. We say the spring exerts a force that is proportional to how much it is compressed. How long is the spring. At time $t=0$ it is the natural, rest length. Then being massless it stays out of the way of massive things by moving, and being made of layers so it gets in its own way it compresses. So the length is actually $L-x(t)$ so the force is proportional to $L-(L- x(t))$=$x(t).$ So $|\vec F|=|kx(t)|.$
So going back to the block, the force it felt was equal to $Mx''(t)\hat x$ which apparently really is equal in magnitude to $|kx(t)|$ now that we did the whole analysis. So, now we just need the signs. Positive $x$ goes to the right, so the force from the spring is outwards (also from Hooke's Law) so in the $-\hat x$ direction, so we get $Mx''(t)=-kx(t)$ for some positive $k.$
So, the forces come from the force law (in this case Hooke' Law). Newton's Third Law tells us the forces come in action-reaction pairs & so you can think of Hooke's Law as telling you how much force it takes to compress a spring or as telling you how much force a spring exerts when compressed. Newton says they are equal and opposite. We know that massless objects move or compress however they need to move until they feel no force (you can think of a slight imbalance making the very small mass move very quickly). And the infinitely massive objects simply don't move at all (you can think of them as moving a super tiny amount).
Edit responding to edit in question.
Absolutely nothing changes except one thing. The spring is no longer being pushed out of the block's way.
In particular the spring is still compressed, the spring still exerts a force to the left on the block, the block continues to feel a force from the spring just as it has since the spring first became compressed.
So let's step back. The spring got compressed because the block had velocity towards it and made contact. During the phase where it was getting more and more compressed it had to be compressed because a much more massive block was pushing it out of the way and so whatever forces they exchanged just allowed the much less massive spring to move however it needed to.
The same things happen now. But now at that moment when it is fully compressed the spring no longer is in the way so doesn't have to get out of the way. But the block still feels a force from the spring so it will accelerate to the left. But remember how the spring is pushing on the right block of mass $+\infty$ just as hard as it pushes on the block of mass $M$ on the left? Well if the block just took off to the left and the spring stayed there it would be pushed by the block on the right. So the block on the right is doing the pushing.
We could experimentally verify this if the block on the right was really another block of finite mass, with mass $m'$ with a pin keeping it stuck in place, and if the pin was pulled out and the block on the right was actually much less massive and the pin was keeping it in place before then indeed the mass $M$ block on the left could stay at rest as the very tiny mass $m$ spring and very tiny mass $m'$ right block shoot off to the right.
This is because to the right block the left one is basically super massive. So there really is a force on the right block and the lack of motion of the right block and its force is what makes the spring push against the left block so hard it makes the left block move.
So the block on the right keeps pushing on the spring, so the very tiny mass spring is pushed with super acceleration to the left unless it touches the mass $M$ block on the left. So basically the spring is still forced (pun not intended) to be in contact with the block on the left, but now it is because of the block on the right, not because of the block on the left. But the same thing happens it adjusts its length at every moment until the length at that moment is just enough to have it push the two blocks just hard enough so they push back equal and opposite to each other (if the spring is massless, and if instead it has a tiny mass then nearly opposite). Here is where we use the third law again.
When does this stop? When the spring gets back to its natural length then it exerts no force on anything and nothing exerts any force on it. Since it is massless the velocity is actually indeterminate. Even if it is attached to the right block, things are still indeterminate. You can't predict everything when you over simplify. But there is a solution, which is the spring and block having no force act on them and being momentarily at rest, just stay at rest. There is a form of the first law that asserts they do this. But of course we don't know the spring is at rest since it is massless so has indeterminate speed. But it is a solution. How about the block. It has zero force acting on it but has a velocity to the left so it just cruises on to the left at a steady velocity.
So the spring is the only thing we don't know about. But you could imagine that if just one air molecule bumps into it and it is massless then it will repeat the process, so it wiggles based in anything touching it. Zero mass objects are quite unstable, so saying where they are and what they are doing is probably a bit much to aim for.
So the mass compresses until the force it feels is zero and the force from the left block is $−Mx′′(t)\hat x$ so it need to compress until it feels a force of $+Mx′′(t)\hat x$ from the right block: I understood the statement but during that time when the right block imparts $+Mx′′(t)\hat x$ on the spring, would not the left block moved more towards right & the value of $-Mx′′(t)\hat x$ changes?
It takes no time under the limits of zero mass for the spring and infinite mass for the right block. Because the mass of the spring is zero, it instantly compresses to whatever length it needs to to experience zero total net force. And the right block never ever moves at all so it needs no time to compress itself to give an equal and opposite force. A real mass on the right would basically be a heavy and stiff spring itself and would take time to compress itself. But since it is infinite in mass it doesn't move so it is at its state of no compression (giving no force on others) and at its state of forcing others (as if it were compressed) ready to do neither at any time and thus needing no time to switch from one to the other.
The spring needs to change itself to itself give different forces, but since it is massless it can do instantly. The infinitely massive block doesn't need to change its length or speed to hive any amount of force or momentum or energy or to absorb any amount of force or momentum or energy.
I truly don't think studying zero mass and infinite mass objects is healthy. But at least it can teach you not to apply results beyond their domain of applicability. Infinite masses can have any amount of kinetic energy even though they never move. They can have any momentum even though they never move. They can compress and exert forces without compressing.
This is because a mass with a huge mass can have some finite energy and momentum while having a truly tiny velocity. And it can exert a force from its own compression with a truly tiny compression.
If you give every object a finite mass then a realistic model would depend on the speed of sound in the spring, not the literal speed of sound in air but the speed at which say a compression wave travels down a slinky. If the left mass hits faster than that speed then something totally different happens (it's a shock, which like speed of sound is a technical term) which is totally different than what otherwise would happen. And even when you hit at less than that speed, it still takes time before the right block starts to move. But this does require the spring to have a finite non-zero mass for the wave to take time to get from one side to the other. And for the mass on the right to move it needs a finite non-zero mass as well.
Since the spring compresses infinitely fast and the right block doesn't have to move it all happen instantly and everything is determined by the left block.
Best Answer
Here is a simpler version of your paradox:
Suppose I take a spring at equilibrium and push on the end of it with a force of ten Newtons. After a very short time, the spring has not compressed appreciably, so the $F=-kx$ law says the force it exerts on my hand is nearly zero, but Newton's third law says it must be ten Newtons. Which is right?
The second answer, that the spring exerts a ten-Newton force on my hand, is right. The spring is a dynamical object. Try thinking of it as 100 springs each with .01 the mass and 100 times the spring constant all connected in series. What you'll see is that the first spring, the one I'm touching, can be more compressed than the second, third, fourth ones etc. The spring doesn't have uniform tension in it any more, which is the assumption behind the $F = -kx$ law.
In other words, Hooke's law is built on assumptions, and when your spring is massive and accelerating differently in different parts, as real springs do, those assumptions fail. Your two springs will exert equal and opposite forces on one another as Newton's third law dictates.