I have an almost 2yo DD and 4yo DD. They have days (today) where they seem to eat constantly, primal or not. I offer healthy choices and only resetrict if it's 30min or less before meal time.
Are you willing to make grain free versions of old favorites? They won't taste exactly the same, but come close. I make pancakes every few weeks for the kids using coconut flour and honey. I make enough for leftovers and they eat them during the week while I go back to eggs. I also make a grain free pizza with mozz cheese and cream cheese for the crust. DH is even coming around on it.
Can you involve your kids in meal planning? Take them to the store and let them choose some veggies that look appealing? The more you include them, the likelier they will go along for the ride.