Feathered Wonders, you give him a very good idea:
Another is to do a search of the local area in Google. There are tons of sites that lead to nowhere in someways - but would love links to anything locally.
I did it for my local portal and I found a lot of good sites to put a link to mine. 
Possibly a paid advertisement.
Another great idea when you start with a site! Actually, I spend just 15€/month with Adwords and with a strategic campaign you can have a very good return! For a restaurant, I think you certainly must spend more
but you can think about it