So he's allergic to egg whites, how can your wife discredit an entire way of eating on that basis alone? Iron deficiency is actually the most commonly seen nutrient deficiency in children. Perhaps you'll have to give him mashed up meats for protein like ground beef, turkey and pork instead of eggs.

From Wikipedia:

Egg whites, which are potent histamine liberators, also provoke a nonallergic response in some people. In this situation, proteins in egg white directly trigger the release of histamine from mast cells on contact.[15][16] Because this mechanism is classified as a pharmacological reaction, or "pseudoallergy",[15] the condition is considered a food intolerance instead of a true IgE-based allergic reaction. The response is usually localized, typically in the gastrointestinal tract.[15] Symptoms may include abdominal pain, diarrhea, or any symptoms of histamine release. It can result in an anaphylactoid reaction, which is clinically indistinguishable from true anaphylaxis, if sufficiently strong.[16] Some people with this condition tolerate small quantities of egg whites.[17] They are more often able to tolerate well-cooked eggs, such as found in cake or dried egg-based pasta, than loosely cooked eggs, such as fried eggs or meringues, or uncooked eggs.[17]

How is his vitamin C intake? Not getting enough of it can affect iron absorption.

Iron Deficiency in Children

Suggestions for what? Substitutes for eggs? How to convince your wife to let your son stay paleo? It sounds like you're on the right track- just avoid eggs for 30 days, then reintroduce yolks. I would try to mix grass-fed liver into as many of your son's meals as you can (easy to do with ground beef and spices). I can't imagine a better fix for the anemia than a diet rich in organ meat and grass-fed muscle meat and low in lectins, phytates, and dairy.

When a child is undergoing a growth spurt, which could be typical in a child the age of your son, iron levels can be temporarily low. I'd be cautious of throwing out an entire way of eating based on one lab test at one point in time. Does your child have other symptoms of anemia that would be worrisome, or was there just one unrepeated lab test upon which the pediatrician based his "diagnosis"? If it were my child and he was healthy overall, I'd continue doing what I was doing, and reevaluate at 18 months. But then I'm no fan of the medical establishment. :)

Meats and leafy green vegetables are better sources of iron than grains. Not only that, but the type of iron found in meats is heme iron, which is the type more readily absorbed by the body. The iron in grains is non-heme, which is harder to absorb, which is compounded by the phytates, which further inhibit absorption. This PDF is pretty helpful: http://www.mckinley.illinois.edu/handouts/pdfs/dietary_sources_iron.pdf. Personally, I'd be more tempted to add baked potatoes to his diet for the iron than grains.

The larger issue to my mind though is that your wife is worried about harming your child through diet. Perhaps reading Sarah Fragoso's Everyday Paleo website or book, or some of the paleo parenting websites, would help her see that children can be perfectly healthy eating this way. You're not depriving your child because you don't feed him whole grains.

I'd leave off the egg whites indefinitely, and maybe wait several months before reintroducing egg yolks. (The lion's share of the nutrition is in the yolk anyway, with the white being almost completely protein.) If you're not feeding your child processed foods, you can easily avoid egg whites or other egg proteins, so why subject him to allergy testing, which can be painful? Just my $.02.

Edited to add: Is it Mark Sisson or Robb Wolf that did a comparison of the nutrition in a paleo/primal day's diet versus a day of the SAD? Maybe showing your wife that comparison would help ease her fears?

I say get off the paleo diet and go on a diet of meat and veggies instead. Egg yolks are not absolutely necessary. There is also no need to bring in wheat, since starchy tubers and rice should do just fine if there is no allergy.

Medical doctors have literally a few hours of nutritional training in four years of schooling. Unless your doctor has studied nutrition on his or her own, then food issues are outside of the scope of their expertise. Allergies begin with leaky gut, and always need to be addressed as a digestion issue. My advice would be to find someone who knows this that your wife trusts, and get digestive support for your child. Some naturopaths can give you this kind of help, as can nutritional therapists through the Nutritional Therapy Association. I would imagine that having a health care professional say similar things that you've been saying could be very reassuring to your wife.