I have a website that I built about 8-years ago and, instead of fixing the website, I've decided to rebuild it. It's nearly an exact rebuild but with a newer CMS and extensions. I'm 301-redirecting the old menu links to the new website so of course Google won't index the pages anymore but I'm also getting emails from Google Webmaster tools warning me about the pages no longer being crawlable and indexable because of my redirect. Does this mean I may not get the benefit of a redirect, that page having moved and my backlinks and stuff all carrying over to the new website for SEO or should I have just left the old website pages up and just added a backlink on the page to the new website?
No that is normal since you did 301 redirect, non canonical will never get indexed. The new link may or may not be index by search engines.
There can be an error in your redirections. Maybe your redirects ain't working properly and creating an issue in Google's crawling or indexing process. Check the settings of your redirects and correct them if anything is causing a problem.