It depends on exactly what happened to the previous locations.
1. If they've ceased operations, I'd add a **disused:** (lifecycle prefix)[https://wiki.openstreetmap.org/wiki/Lifecycle_prefix](life-cycle prefix) [lifecycle prefix](https://wiki.openstreetmap.org/wiki/Lifecycle_prefix) to the shop and/or amenity tag. If a different business reopens in the same location, the previous element can be re-used to help [keep the history](https://wiki.openstreetmap.org/wiki/Keep_the_history).
2. If they're still operating under another name, simply change the name and/or brand tags. (And if you don't know the new name, just omit the name tag -- someone will add it eventually!)
If you're not sure, I'd go with #2, omit the name, and add a **fixme** tag or a note that will cue other mappers to survey the place.
If you question is "how to remove them all at once" there's no real shortcut here. You could propose an [automated edit](https://wiki.openstreetmap.org/wiki/Automated_edits), or set up a group mapping project using a [tasking manager](https://wiki.openstreetmap.org/wiki/Tasking_Manager), but at this scale it's probably easier to simply make the changes yourself, or with a few other mappers.