You may hear from some people on here who are way more strict than me, but here's my point of view: a carb is a carb. Yes, a bowl of cereal might be less nutritionally dense (in terms of vitamins/minerals) than a plate of vegetables, but if he chooses to make that trade in favor of the cereal, it's not going to throw him off the wagon. Encourage him to make a smart, healthy selection when it comes to the cereal. A plain puffed rice cereal (white rice is considered paleo by many, because it's a clean starch with the gluten removed) with almond milk and stevia sprinkled on top is really delicious, and my go-to when I'm craving cereal. To make it more satiating, he can sprinkle it with protein powder instead of stevia. And you'll be surprised -- because puffed rice grains are puffed to approximately three times the size of normal rice grains, a whole cup usually has only around 10-15g of carbs.