Just a thought about when it is more effective to promote.
Some days ago, talking with a guy who has a top selling app (and is kind enough to give good advices), he reminded me that, besides the app quality itself (and many other factors, among them, a bit of luck), there is a big mistake which some programmers do quite often, and can decrease the app chances to be discovered.
When we first release our app, it is somehow promoted by Google, appearing more "easily" in the lists. Some of us, after a hard work, and when the app is "technically nearly finished", are in a hurry just to release it as soon as possible, and decide that we will improve it or even fix some already known small bugs later . These small bugs or the sensation of "unfinished product" lead to a higher uninstall rate. After this short period, when the app stops being "promoted for free", slowly dissappears from the lists unless it has had a good start.
So, IMHO, any effort (paid or not) made to promote your app will be more effective if made when it is first released, and if this first release has been polished enough