Your print shop is giving you old and outdated advice. There are a number of issues with outlining all of the type in a document only one of which being that the content is no longer editable. The second is that outlining type tends to "fatten" the appearance of the type.
I'll get off of my soapbox now for a second. To answer your actual question. What you'd need to do is override the page number on each page of the document to make it available for outlining. In the pages panel, select all of the pages in the document, then from the Pages panel menu, choose "Override All Master Page Items". This will release the page numbers (along with anything else on the master pages), and make them available on each page of the document where you'll now be able to outline them.
But again, this is a lousy workflow. If the printer is worried about the fonts, why not just output to a PDF file with fonts embedded and provide that to the printer? I know we're getting into the weeds with this discussion but if your printer isn't willing to accept files that are not outlines, you may want to look for another printer.