To give it to you straight, you go in exactly the way you are but fully prepared to be flexible. There are vegetarians who are butchers. Diabetics who are pastry chefs. Chefs who never taste their food but make amazing things just by using their sense of smell. You make it work if that's your love. Knowing as much as you can about food will do nothing but make you valuable, expand your horizons, and eventually allow you to do what you want to do in the kitchen.
Also, unless you are Julia Child reincarnated, no kitchen is going to let you come in and immediately make changes to the menu. That is an honor that is earned and you will eventually be able to do so. But if you mess up - oy! Have fun picking herbs for a month :)
Just because you are eating Paleo doesn't mean you can't cook mainstream foods. If you are working in a SAD restaurant all you can do is try to improve recipes to make them more Paleo friendly, like using butter, coconut oil. etc. instead of soy oil for example. You can make options available such as Paleo burgers wrapped in lettuce leaves instead of buns.
If you need to go to a culinary school to train for the job I don't think you have any other choice than to train their way and eat your way. Once you are trained you can choose to open your own Paleo-ish eating establishment.
I have a bon ami who went to the CIA and he said that there were several vegetarians in his class. They still had to complete butchering 101 if they wanted to matriculate. I guess there would have to be a 100 precent Paleo school if you want to avoid cooking the NADs. Or you could cook them and not eat them. Kepp us informed if you find a program that meshes well with Paleo. It would be interesting.
I'm a paleo chef.
I went to Bauman in Santa Cruz and got my Natural Chef cert. It was an okay experience. I've had to learn a lot on my own, which is sad, considering I paid 10 G's for the program. There was a heavy vegan/vegetarian bias as well as some wierd spiritual (Mother Earth/Father Sky) hippie stuff. Don't get me wrong, I can hang with the hippie crowd... but Paleo cooking needs to have a factual/scientific base to it or else people won't believe anything you say.
I did learn a lot about nutrition and cooking techniques. Although the hands on part seemed to be lacking (especially with preparing meat) and the instructors were, oftentimes, guessing about things they knew nothing about.
Maybe a different location will fare better. And the nutritional counselor program appears to be a bit more comprehensive.
So, depending on what you're expecting to get out of it, you could be disappointed or feel enlightened.
I wasn't strict paleo while I was there, but you're never forced to eat things if you don't want to. I rarely had anything grain or legume based, but every once in a while I had some corn based dishes or a bean soup. Never any gluten or soy.
There is one option: Natural Gourmet in NYC. It's not 100% Paleo or anything, but it's a start. They source mostly organic ingredients and use healthy cooking methods, if that would make you more comfortable.
Read more here: http://naturalgourmetinstitute.com/html/chefs-training.html
From their philosophy page:
"The Natural Gourmet Institute was founded on the principle that what we eat significantly affects our physical, mental and spiritual well-being. Each individual reacts differently to food and so will thrive on a unique diet. Consequently, there is no one perfect food or dietary regimen that works for everyone. With these principles in mind, The Natural Gourmet has created a framework for healthy food selection based on specific criteria for high quality ingredients, concepts of eastern/western nutrition and a variety of dietary paradigms. To accomplish this goal, we look to the whole food traditions of our healthy ancestors as well as to modern scientific studies. Our approach empowers people to tailor their eating style to support their individual health needs Our focus is health-supportive, whole-foods cuisine, with an emphasis on traditional unrefined ingredients. It is mostly plant-based, but good quality products of animal origin have a place in it as well
The following foods are used in our classes:
fruits and vegetables* organic whole grains organic poultry organic legumes organic eggs organic soy foods organic sea vegetables organic natural sweeteners nuts and seeds* seafood
*organic when possible"
So again, not really Paleo, but they are very open to different diets and utilize organic ingredients for the most part.
Bauman College has a Natural Chef program, too. http://www.baumancollege.org/programs/natural-chef.html
Real Paleo Hacks 8 Answers
The Next Paleo Chef 0 Answers
Any Food Fermentation Advice Out There? 3 Answers