Which version of the script (JS, AS, VB) are you using?
Sorry ... left that out.
Indeed, it can't be done directly with a findGrep (or findChange). Look at the dialog box in InDesign and you'll see that the paragraph rules are not included. Since the JS Find features leverage the technology that provides the find features to the interactive user, it suffers from the same limitation.
In a script, you can get around this by doing the find (rather than a change) and then iterate through the results setting the paragraph rule you want.
Thanks, Dave ... I should have noticed those features are not available in the find/change dialogs (and will keep that in mind next time I'm looking for some attribute to apply).
I've worked around the issue by duplicating the basic paragraph style, but with the ruleBelow active, and then simply apply it through the findChange control file.
I had hoped to avoid having so many styles ... perhaps in the next release!