Go to the medic when you get there. He will issue you a drinking straw. Now here is the important part, follow the directions exactly and suck it up.
It sounds like you are trying out for some sort of spec ops unit (like our Rangers). You will run, a lot.
There is no other way around it, running is the only way to get better at running.
You didn't state if this is your initial entry in to the military, but if it is you will not be having "free time" to hit the gym when you want. This is just a part of initial entry/basic training.
Here is what you should be doing in order to get ready. I'm not sure if the Danish military is anything like 'Merican Army, but here it is.
Running (work up to 4 miles every other day)
Calisthenics (pushups, jumping jacks, mountain climbers, air squats, etc.)
Bodyweight excercises (pullups, dips, rope climbing)
That is it. Basically DON'T WORRY about your "gym body" or your bench going down. This is a different kind of life you are about to learn. The military gears you to go for endurance which is important on the battlefield. You do need to be strong, but what does it matter how much you can bench if you fall out after walking 20 minutes in 120 degree weather wearing 80 pounds (30 kilos) of gear.
Once you get past the basic training and get to a regular unit, you will have time to hit the gym. Focus on becoming a running/calisthenic machine and you will smoke basic training in the physical part. Once you get to your unit it gets better.