If he wants to improve recovery then it'll simply be a matter of eating more protein or more carbs. One would assume, eating paleo, that it's more likely that he's eating adequate protein and inadequate carbs, so that's the logical adjustment to make.
It will also be beneficial if he eats the carbs/protein relatively close to the end of the workout (we're talking a matter of hours here, not minutes as is regularly assumed), since his muscles will be relatively more insulin responsive. From what I've been reading there may be something of a threshold effect, whereby minimal carbs will be channelled away from muscle tissue to the brain, but given plenty of carbs (and thus temporarily heightened blood glucose) glucose will be used to refuel the muscles.
Providing he's eating adequate protein (1.2-1.7g/kg), then I'd advise adding more carbohydrate rather than protein. Eating more protein above and beyond that required to optimise nitrogen balance won't bring any further than carbs and will be substantially more physiologically stressful (e.g. on kidneys, liver, glycation etc). The glucagon response will only work against his aims, by offsetting the insulin that is signalling for fuel uptake by his peripheral tissue (in this case, muscles), forcing tissue breakdown and energy into his bloodstream. Adding carbohydrate, conversely, will replenish glycogen and keep amino acids in the tissue rather than allowing them to be broken down, via the effects of insulin and also via reducing the body's need for gluconeogenesis. At a macro level (and there may be nothing in this other than what I've already said) it also makes paleo sense that the presence of carbs, denoting plenty and 'feasting' would encourage growth and recovery of muscle.
One thing to be said for 'freshly killed' meat is that it will contain a lot more creatine (before being thoroughly cooked), which is integral to growth, recovery and performance. If he's not a fan of rare meat then he could consider creatine replacements.
Eating protein before or during workouts has been shown to be fruitless for performance.
I wouldn't say that there's any benefit to having a protein shake rather than meat. The food will be more nutritious, which can only help recovery. There's a good window of time in order to benefit from improved muscle insulin responsiveness, so ingesting protein within minutes simply isn't necessary, although admittedly having it quicker will only help. It also depends on what sort of protein shake you were to use anyway: casein will be broken down very slowly anyway (and I doubt it's goat/beta-casein!) whereas whey may be more beneficial for recovery and growth, precisely because it is so insulinemic and easily digested.
Also make sure he's getting his cholesterol!