The main problem is usually protein. Plant proteins are concentrated in the seeds (not the leaves, stalks, and roots) which are the heavily defended/allergenic parts that primal tends to minimize. Vegetarians have a much easier time if they eat eggs, yogurt, cheese. The least awful vegan source is probably potato protein powder.
Fat would be oily fruits--coconut, olive, avocado, cocoa. Vegan products seem heavy on the refined oils--no matter how "expeller pressed" or expensive they are it's still a dangerous concentration of linoleate to be consuming. Definitely ditch these first.
Carbohydrate recommendation would be the same: more tubers, squash, fruit--less sugar and grain. Rice is mostly harmless if he needs simple volume/calories.