The acceleration is not really central to your question; we could ask essentially the same thing by considering any object that is not accelerating, but whose mass is changing.
To restate your point: in the object's own rest frame, there is no net force on the object, since the velocity and acceleration are zero. In a frame where the object is moving, its momentum is changing, despite there being no force on it, leading to an apparent paradox.
I think the resolution is that, if things could magically gain or lose mass, Newton's laws would not obey Galilean invariance. Of course, there would also be no energy conservation, no momentum or angular momentum conservation, etc.
In Newtonian mechanics, if a cart gains mass, the mass is coming from somewhere, e.g. someone pouring sand into it.
So imagine a cart rolling along the ground to the right at constant speed $v,$ and someone pouring sand into it from above. We can think about two scenarios:
- The sand is also moving to the right at $v$ as it falls.
- The sand has no left/ right movement as it falls.
In scenario 1, there is no external push needed to keep the cart moving at constant speed. As seen from the ground frame, the system of the cart plus any sand in it gains momentum to the right, but this momentum came in from the sand as it entered the system. As seen in the cart's own frame, the sand has no left/right momentum and the momentum of the system isn't changing. Both perspectives tell us we don't have to push on the cart.
In scenario 2, both perspectives say we do have to push on the cart. In the ground frame, the cart is gaining momentum without the sand bringing that momentum in, so we have to push with a force $F_{\rm push} = \dot{m} v$ where $\dot{m}$ is the rate that the sand adds mass to the system of the cart and any sand in it. As seen in the cart frame, the sand is moving to the left at $v,$ bringing in momentum per unit time $-\dot{m} v,$ and we need the same $F_{\rm push}$ to keep the momentum of the system at zero.
In either scenario, Galilean relativity holds. Observers in any reference frame can apply a Newtonian analysis and agree about whether there must be an external push on the cart, and on the magnitude of that push.
What remains to be resolved is the exact semantics of "force". In scenario 1, in the ground frame, the sand is bringing momentum into the system of the cart plus any sand in it. If we define "force" to mean any flux of momentum into a system and include systems where mass is flowing in or out, then the sand is "exerting a force" on the system as it falls in the cart, and from the cart's own reference frame, the sand is not "exerting a force" on the system. In that sense "force" would not be a Galilean invariant. I don't think this is usually what people mean when they say "force", though. Instead, they usually mean whether or not someone needs to push on the cart to keep the velocity constant.