Change all the paragraphs in that frame to ONE new paragraph style?
whenever a certain character is found in a graphics frame
Characters appear in text frames, images in graphics frames, so I'm assuming you meant text frame?
find/replace to say whenever a certain character is found in a graphics frame, change all the paragraphs in that frame to a new paragraph style
In the screen shot below, I'm searching for the ® symbol (^r) and changing the paragraph format to Sample Para Style: