Short answer, when you know it will pay off.
Long answer, PR gets the word out people to your site/app. If you haven't proven (on at least a small scale) that you can convert these people to users/customers, then you're wasting your money on a PR agency, and worse, you might be doing harm to your brand. My advice is to build your first sets of users by hand, one by one, listen to them and adapt your product until you sense they have become emotionally connected to it. Then amp up your marketing mix, PR being the first (in my opinion). An initial contract could be $5k per month, with the sole purpose to position the company to publications that achieve a specific goal (fund raising, user growth, brand credibility, etc). Contracts will ramp up to $15k-$25k per month after you've proven the value.