In a search & replace window, under "other parameters" there is "format" option:
it is possible to make replacement text formatted as "bold" or "understrike", but I can't specify style (as it was in MS Word ancient versions)
same problem with "find" field: say, I can't find all occurrences of "paragraph" with style "Heading 1" and replace it with "Heading 2" style
Such an enhancement request was previously made:
Bug 89974 - Feature request: Option to select all instances of a style via the Styles and Formatting Panel
Other options allows, by checking Paragraph Styles under Other options, to do what you are searching, including all occurences of those paragraph styles by Find All and/or Replace All.
*** This bug has been marked as a duplicate of bug 89974 ***