Thank you for doing the work. More of it needs to be done. I don’t know what your workflow is, but running Android-x86 and injecting into the virtualbox networking process to strip the SSL should still work, unless the app uses certificate pinning. I wish I remembered the name of the program, but it’s specifically for injecting into a running exe and hooking all network calls to pull ALL network data from that specific app. It’s not Fiddler or Wireshark or any of those. Fiddler and wireshark will work fine if you add your self-signed cert to the Android CA list, as long as certificate pinning isn’t used in the app. You can point wireshark to the virtualbox network adapter so it doesn’t listen on your other adapters. Also, most apps in the app store, play store, and F-Droid likely will not have much maliciousness. Play Store has the highest chance. But I think you’ll have better luck using all the major search engines and searching for “free VPN android” without any adblockers, using an android phone (Google & co easily detect user-agent manipulation) running chroming. Making note of all the paid ads, and then getting the first 10 pages of URLs, and then comb those links (all the ad links & result links) and download any .apk that shows up. Keep an eye out for more ads on those pages as well. Use a fresh android-x86 for each analyzed VPN apk.

There may be a better, easier way, but this was how I quickly analyzed the network data of android malware as of a few years ago.

Edit: other keywords to find shady vpns are ads for things like “watch porn in Utah” and “express VPN”, " nord VPN", etc. You’ll want to do the search within android as Google and Bing will allow the malvertisers to target specific operating systems, along with locations and other variables.

Also for checking into the servers that show up, and any interesting domains, you can use shodan and similar tools, and there is a great site (name escapes me now, similar to domaintools and urlscan.io though) that shows what domains run on certain IP addresses and also the owners and creation dates, although cloudflare and private whois entries make those less useful today. But that will potentially allow you to unmask ‘networks’ of shady free VPN providers.