how to indicate that restaurant moved?

As you don't post more details, I will try to guess the answers:

1. Notify local mappers
   If you just want to push this information to the (local) OSM community, you can add a "note" (osm.org, right toolbar, last button) with a marker. In the textbox you can add an description saying what moved from, to and a source/proof for your hint would be great for everybody that likes to check if it's right :)
2. Move a POI in OSM
   If you are able to edit OSM on your own, you can move the POI of course. For example in JOSM you download the current area with the POI, then the new area. Then by pressing F3 you zoomout so both areas are visible and you can just drag the POI to a new location. Maybe you want to merge the POI with a building outline, that can be done by CTRL+C copy the object to clipboard and CTRL+SHIFT+V on the selected building outline to paste all the tags. Don't forget to give good summary in your edit commit message.
3. Tag restaurant that it had been moved
   Currently OSM has no good/unique way to model time based informaton: http://wiki.openstreetmap.org/wiki/Comparison_of_life_cycle_concepts
   A simple idea can be to keep an information as old_name=* tag at the old POI, so it may help people for orientation ("go till the building where XYZ was in before..:").

If the POI is a node, the best for OSM is to move the existing POI to its new location, therefore we preserve its history. If the POI includes address tags, then update the address. For the previous location, you can create a new node for its new feature (e.g. a new"shop" key + new "name") or if it's not occupied at the moment, a tag "disused:shop=yes". In addition, you could add a tag "note" explaining that the old shop has been moved or a tag "old_name" containing the previous shop name.
If the POI was previously on the building polygon, it might be easier to move the tags from the previous building to the new one and update the tags on the previous building as I said for the nodes.