I can see the plugins they downloaded on WordPress but I can't see a link to their websites.
If you genuily believe your service solves a problem those WooCommerce users have with their websites, why don't you start by contacting them one on one?
If you can see the plugins they downloaded and I guess there will be a way to see their profiles (maybe in wodpress forums) and contact them, you can send a few messages/emails to those website owners.
Like: "Hello, I noticed that you are using WooCommerce blah blah... if you, like me, are experiencing this and that problem, did you know there is a simple plugin/solution/service that can quickly and easily solve your..."
Just a staightforward, honest and direct message.
This technique above can be used assuming you are in the beginnings of your service, which you should be at the moment.
Another idea is to post on WP forums or why don't you even make an informative YouTube video, presenting the problem your service solves and then linking to your sales website.
Feel free to let me know how that sounds.
Tip: Have you tried creating Facebook ads with "WooCommerce" (and variants) as Interests?
Campaigns with specific interests and a few demographic filters are quite effective. Especially now that Facebook aggregates data from other online and offline sources.
Good luck! Let me know if you have any more questions!
I explain how to do it here http://linkedexpertsalliance.com/topic/how-to-find-fresh-new-clients-on-linkedin/
If you want to code it yourself, find a big list of domain names. Create a script (I use PHP-CLI) to download the homepage of all of them and look for some kind of meta tag that only WooCommerce has. Load that script on a Linode with tmux and let that run for a few hours in the background. Now you have a nice list of domain names with WooCommerce. If you want to save time, let me do it for you. If I like your service, maybe I'll sell it for you for a commission.
To help in cold-calling, you may want to use a service like www.builtwith.com or www.perfectleads.com. You may also want to go the path of Google Ads. It's been highly effective for many business owners.
Additionally, if you build a free plugin that ties into woocommerce, you can get a number of your target audience to download the free plugin (as long as it's useful, and hopefully pre-sells your woocommerce product/service).
Hope this helps.
I definitely recommend trying something like BuiltWith. It's going to cost you a bit of money, but you can get a nice list of domains and then start reaching out to those people: http://trends.builtwith.com/websitelist/WooCommerce
Also consider partnering with other sellers of WooCommerce items. I own a site called https://wpovernight.com/ and our plugins are running on well over 50,000 WooCommerce stores.
Finally, consider releasing a free version of your software as a plugin on WordPress.org. It's a huge (and free) marketing channel. Feel free to schedule a call with me and I can give you a bit more advice about ways you can reach a WooCommerce audience. :)