Violating Newtons First Law!

If you say that pushing against the box (and the box pushing against you) is an internal force, then that means that you and the box are considered to be two internal parts of a single object. The center of mass of this object does not move when you push against the box, since all forces are internal. So you will move in such a way that the center of mass of you and the box does not accelerate. The net force on this object is zero, and the object does not accelerate (if it accelerated, then its center of mass would also accelerate), so Newton's First Law is fulfilled.

Internal forces can make things move. Nothing says they can't. It's just that any internal forces have an "equal and opposite force" that is also internal, so momentum is conserved, at least when considering internal forces. This has everything to do with Newton's third law and nothing to do with Newton's first law. Newton's first law says nothing about the distinction between internal and external forces.

If you want to apply Newton's first law, all you say is "I was at rest, the box pushed on me, I experience a net force, so I start to move."

Your confusion stems from the misunderstanding of the term "internal force".

Internal force in this context is not a force which acts from the geometrical inside of some body. It is internal in the sense that it results from the interaction of the parts of the system, whose collective motion (the acceleration of its center of mass) you are considering.

So when analysing the motion of the whole system (the box and the person together), we see that its center of mass has indeed not accelerated. But if we consider only the box, we see that it had accelerated, but Newton has no need to worry, as an external force (your hand) had caused the acceleration.

You are right, the force is internal to the system and not just the box. Overall the combined center of mass will remain fixed as you and the box exchange momentum.

There is no paradox here because you are either considering the entire system of box + human with no external forces, or you are considering the box by itself with an external force applied (by the human).

System box
You exert an external force on the box and the box accelerates.

System you
The box exerts an external force on you and you accelerate.

System box and you
You exert an internal force on the box and the box accelerates.
The box exerts an internal force on you and you accelerate.
These two internal forces are a Newton’s third law pair.

There is no external force on the system and so the centre of mass of the system does not move.

The linear momentum of the box is equal in magnitude and opposite in direction to your linear momentum.
The total linear momentum of the system had an initial and a final momentum of zero.

The thing with internal forces is they can't move the center of mass. And in this case too, COM remains fixed. And let me make it clear, its$$F_{net-external} = m_{total} × a_{COM}$$ In your case $F_{external}=0$ and so $a_{COM}=0$. This doesn't comment of individual acceleration of parts of the system.