Well, according to Kruse, and I think that those who have done ok on Paleo diets will tell you, regarding the business of health and fitness, that maybe 80% of fitness is about having enough of the right nutrients for growth, maybe 15% is exercise, and slow cardio exercise is NOT good for you, because it reduces your adaptability. This is how the 'hard exercise' paleo theory works.
Once you expand the ceiling on your strength and speed and reflexes, you can simply, when needed, sustain a lower level for a longer time. Running, especially in typical mainstream running shoes, is actually very damaging to the body. Hard exercise can cause more acute injuries, but it also leads to more rapid development - as you probably know, muscles grow because you tear them, and light cardio does not tear muscles, it compresses bones and cartilage and wears out joints, and increases oxidative free radicals, because this type of sustained exercise requires a big surplus of available energy.
Also, if your body is permanently stuck in sugar metabolism mode, you will find it difficult for your muscles to adapt properly to drawing more energy from glycogen, which sets the ceiling which makes the marathon the longest sustained cardio exercise that a human can do, in fact, it often is beyond the limits, and the muscles actually decay from doing it regularly because of running out of glycogen and needing to manufacture more, without enough available material to make it, leads to autophagy (consuming one's own cells).
The paleo hard-exercise route for developing fitness is the most reliable method of training the muscles to accumulate maximum optimal glycogen, and once that's fixed, you can run a half marathon easily.
I have to also point out, that exercise, without addressing the metabolic/dietary issues, actually depletes the immune system. Even resistance exercise does this if you push too hard, simply, the immune system will lose some of its resources for fighting infection, instead applying them to repairing the damaged tissues, and then you get sick.
I personally hate exercising in summer, with the exception of swimming, and I'm not really a water baby at all, I'm a bit like a cat, sorta have to fight my instinct to flee from cold and suffocating things.
You will learn a lot from reading Kruse's blog. He explains why sometimes paleo does not work, when carbs are ok, and such a comprehensive model of evolutionary quantum biology that will make your brain melt.
OH, and I have some experience with training without adequate diet. When I was in remand for 7 months, stuck in a box with 4 other people all the time, one of the things I started doing was a full bodyweight resistance training and flexibility program. I hit a brick wall with the weight training, because simply, there wasn't enough proteins and fats in my diet (especially fats) to allow my muscles to actually grow. Several of my cellmates during that time also were very interested in exercise as well, and I remember specifically this macedonian coke smuggler/dealer guy I was in with for 3 months (he was one of the best cellmates I had over 12 months inside) he said that diet is the most important factor, given that you are actually doing the exercise...