After launching a couple paid search campaigns we got the first attributed paying customer.
The main keywords for my competitors are really expensive and out of my budget, so I used the "People also search for" feature on Google to target other, less expensive keywords.
This strategy paid off! Assuming I can replicate this model paid search will be a great channel for this app :)