You need what's called a wildcard search. In the search and replace dialogue, click on More and check the Use wildcards box on the left.

From the MVPS site:

You can use ranges of characters in exactly the same way as with [ ], thus [!A-Z] will find everything except upper case letters.

Thus, with ^p and this, you should be able to find lower case paragraph openings.