I did paleo for awhile, and it is not hard. What's hard is feeling "different" from the crowd you are in or feeling like you "miss out" on something you want. Don't expect perfect, but expect an A (90% correct). I don't mean to plan to stray, but if you do for a few bites, don't beat yourself up. Grok didn't have the temptations of donuts, snicker bars and big macs, and you always will.
One of my mottos is to only stray from my plan when it's worth it. I don't stray for things I think are "OK," I hold out for things I LOVE. Corn on the cob only in season, cheesecake only if it's the real NY style, good stuff, etc. Become a food SNOB of sorts.