I like to think of different exercise 'programs' along a line of a continuum. Let me first say that I think that all the things I will mention are very useful and can increase health within a paleo-framework. Of course this implies proper recuperation time and individual planning.
The far left of the continuum is living like a hunter-gatherer: total re-enactment. All the benefits of an outdoor physical active life, but also all the risks. This is what the human organism expects: natural 'cross-training' (strength, metcon, sprints, speed, agility, endurance, stamina, coordination, balance, low & slow, ...), lots of different kinds of movement with power law variation, biomechanically suited for our organism, and with the social and environmental, biophilic benefits on top.
On the far right side I would put HIT, BBS type exercise: very hard, not especially fun*, in a rather sterile environment, but safe and very effective and efficient. This is very much bang for the buck, but without the extra benefits mentioned above. Of course, no one keeps you from hiking and playing outdoors in between the exercise. But, in my opinion, one HIT training a week isn't anough, we need those things too!
MovNat and Crossfit would be in between those, with MovNat more towards the left side, and Crossfit, more towards the right side.
Again, respecting individual needs and recuperation, all of these I consider very useful for optimising health within a paleo framework!
My personal training is a mixture of some weight training and sprints and some outdoors MovNat training. In an ideal world, it would only be outdoors MovNat training, with a social aspect to it, and some play. But weights and sprints, especially in winter are more convenient for a working family man. Still, the spirit of the workout is very MovNat minded.
*I know that this kind of training can be fun in some weird, masochistic kind of way ;), especially afterwords, but not the fun you get playing a sportsgame...