Who decides which restaurants are allowed to operate within a DoD base? How does the approval process work?

CPT Aaron Kletzing, like many of the answers, "it depends". If it's a standard commercial enterprise operation, it would likely be a concession operation overseen by AAFFES (in fact, AAFFES is usually the 800lb gorillia in the process). If the commercial operation is part of an MWR program, then that goes under another set of criteria. etc... etc... Of course, the base commander gets a vote regarding any commercial entity operating on the installation.

However, regarding the approach you're talking about (healthy .. nutritious .. low cost .. etc.) this is something that would probably fall right in line with the DOD's Food Transformation efforts* that have been going on for the past few years, so it would likely get something that is streamlined if presented properly.
-----------------------------------------
* https://www.health.mil/Reference-Center/Reports/2021/07/28/Military-Food-Transformation
Other references:
- https://www.esd.whs.mil/Portals/54/Documents/DD/issuances/dodi/133009p.pdf
- https://www.esd.whs.mil/portals/54/documents/dd/issuances/dodi/133021p.pdf
- https://www.esd.whs.mil/Portals/54/Documents/DD/issuances/dodi/770018p.pdf
- https://www.esd.whs.mil/portals/54/documents/dd/issuances/dodi/101513p.pdf

AAFES:
https://www.aafes.com/about-exchange/doing-business/services-vending.htm

There are two basic options to sell through our Services and Vending program:

Short Term Commodities - managed by the local exchange at each military installation. The contract is administered on a temporary or roving basis, and Retail Merchandising Units (RMU) located in the retail mall area are provided to concessionaires to display and sell merchandise. Products are limited to cash and carry items only.
Long Term Concessions - program provides opportunities to operate permanent locations. These contracts are competitively solicited by contracting officers at the Exchange headquarters in Dallas, TX.

To learn more about concession business with Exchange Services and Vending dial [login to see] .

For referrals by local Services Business Managers complete a new application and return it to the local Exchange.

For businesses with regional or nationwide opportunities complete a new application;
https://www.aafes.com/Images/doingbusiness/sourcelist-sdv.pdf

Follow the money... Who pays the most plays the most. I, for one, miss the old AAFES Snack Bar. If you want a Whopper, go to Burger Schnozz off post... Give me an AAFES Burger with Bacon and extra Cheese any day of the week.