>Make a hamburger 'spaceship' (I'm making this one up as I go!):  >have a hamburger patty that looks sorta like a UFO.

Similar ideas have worked for my 8 year old daughter.  Pictures, faces, shapes always seem to work.

Smoothies with fruit, raw eggs, and vanilla, go over well.  Sweeten with a bit of honey if necessary. 

Sliced avocado, nitrate free bacon, and fresh fruit. 

Ground nuts, chopped dried fruit, coconut chips, a bit of honey, makes a nice cereal when topped with coconut milk.  I make my coconut milk at home from whole coconuts, and add roasted almonds into the blender, to give the milk a nice nutty taste.

Don't make the mistake of trying to go paleo AND low carb with your childern.  They're going to get their sugar one way or the other, so you need to scratch that itch with fruit, honey in moderation, and occasional non paleo splurges.

Mark