Those "protected" fonts are Typekit fonts which are not licensed for packaging. There are two options for a printer:
(1) Any printer worth their salt will have at least one copy of InDesign CC. InDesign is the primary application for commerical printing output. If so, they will have access to the Typekit fonts if you're submitting the InDesign file and resources.
(2) You can create a PDF file using the PDF preset recommended by your printer. This is a well-established practice which ensures all fonts will be embedded, including the Typekit fonts.
I am also having the same issues, however, we are not using TypeKit we are using FontExplorer. So, how do I get my fonts to package?
You can also highlight the text and go to Type>Create Outlines. This will make the text into vector objects.
Outlining fonts is a very last resort. It loses searchability in a PDF, not to mention things like underlines, paragraph rules, and automatic bullets and numbering, as well as the "hinting" that fonts use for a better appearance.