JCM--Plz keep us posted how it goes.
After being a vegetarian for many years, (I also eat eggs and dairy), I have started eating some fish, but can't see myself eating meat again. But I am eating a lot less grains, after reading The Wheat Belly book. I have been almost qluten free for the 5 years or so, but even going less grains. Haven't noticed much change, other than I am easily keeping off the weight I recently loss, even when cheating a little more than I should.
I think that even more useful than a strict paleo diet all the time, is the elimination diet. Basically, discovering what does or doesn't do harm to your system.
If you are still have digestion issues, I highly recommend getting tested for low HCL in your stomach. If you aren't making enough anymore, you may need to supplement or do what I do which is drink some lemon water which helps encourage your body to make HCL on its own. It doesn't have to be super strong and you can have it with some sugar or in some tea, but its that tart flavor that sends the message to your brain : hey, make some HCL, I'm going to eat something." The HCL in your stomach tells the valve at the top to stay closed, properly cleanses your food (before it goes into the intestine.), and prevents nasty bacterial issues.
I like the paleo style of eating in general because they encourage people to eat a variety of healthy fats and unprocessed foods. We tend to get far too much omega 6s in our diets and too little omega 3s. Also, by avoiding soy, corn, normal dairy (not organic.), and peanuts, you are by default avoiding many of the goitergens (foods that cause harm to your thyroid, make you feel cold, slow down your metabolism, and are generally bad news.)
I listen to a very informative podcast (which is now a radio show.) called "Revolution Health Radio." with Chris Kresser. You might find it illuminating.
Some of the things that are helpful to some people caused harm to my gut. Flax seed was terribly irritating. Ginger was also equally harmful. Antibiotics can cause terrible damage (although if necessary, do what you must to stay alive.) Too much fiber is a problem. I don't do well with any of those nasty sugar alcohols which are used in 'low carb' or 'low sugar' products. By going paleo, you would avoid that garbage.
Let us know how it goes for you,
Alisha