Please recall that weight and mass are two different things.
Although things may weigh more on a high-G planet, they have the same mass.
Mass is all about inertia. How much force it takes to give an object a specified acceleration (or, when stopping it, a deceleration).
It is exactly the same, on any planet (or even in space), no matter what the G, or the weight, for the same object.
To give an object with a mass of one kilogram an increased velocity of of one meter per second in one second, (an acceleration of one meter per second per second) takes exactly the same force no matter how high or low the G forces, and no matter what its 'weight'.
The same goes for stopping an object. A one kilogram object takes exactly the same force to bring it to a stop from a given speed, in a given time, no matter what its 'weight' (or the G forces of the planet).
What differs from one G-force planet to another different G-force planet, is the force necessary to get it to a certain height and keep it there. Lifting it against gravity, in other words. That is the only time you are competing against gravity.
On a perfectly frictionless horizontal (to gravity) surface, strong enough to resist gravity (hold the weight), it takes exactly the same force to move an object, irregardless of the gravitational force. However, if you are carrying the load, holding it up against gravity, it will take more energy to hold it up. That is, you need more strength to hold it up, and to lift it, but not to move it horizontally.
So your soldiers would not just have a physical adjustment to make, they would have a psychological adjustment to make. They would have to re-learn how to do every physical task. In order to accomplish the same objective, on a lower G planet, they have to move slower and on a high-G planet, they have to move faster.
That is, when the soldiers return to a lower-G planet, they would have to slow down in order to successfully accomplish the same tasks.
This is perhaps counter intuitive to normal human thinking.
So would they have a combat advantage? Not necessarily. Depends on how well their mind could adapt and transfer the skills. But certainly, a combat soldier equal in strength that is used to and trained in the gravity of a planet would definitely have an advantage over a soldier equal in strength, but trained on a higher-G planet, at least in the short term.