It's possible to search and replace paragraph styles. It should also be possible to search for frame styles and replace them with another frame style. It's more abstract than searching for strings, but found frames with a certain style should be marked and then could be assigned with a new frame style by the user with the replace button.
Ok -> NEW