How about grilled barbeque whatever meat you want.
Make your own primal sauce, with tomatoe paste (or fresh if you dont mind cooking it for a while), garlic, onion, a little pineapple for sweetness, apple cider vinager, water, and olive oil (gives it a nice shine). Put it all in the food processor until its smooth and adjust ingredients until it tastes right.
grilled asparagus wrapped in bacon and spagetti squash in a lemon pepper butter sauce for sides. Maybe even a sweet potato since they are not used to being primal.
Desert would be a banana split lengthwise, fried in butter, to caramelize the sugars. A little 98% cocoa chocolate drizzled over it... and maybe a spoonful of whipped cream on the side if you are ok with dairy.
A decent bottle of red wine will wash that all down well.
People tend to think of sweet food when they think of stuff they love. I want them to think of rich and savory when they think primal. Make it decadent with the good fats and oils.