But using Shift>select won't work if the paragraphs are not contiguous.

When I need to do this, I place the cursor in a paragraph with the relevant style, pull up the Styles sidebar via the Format> Styles menu, choose "Select All", and press Delete.

The provisos Susan refers to about being sure you don't delete something inadvertently apply here too.