I don't know what the solution to this is, but I know a few trusted/legitimate companies that sell their user data for around £20/year even after having monetized their users with actual money I will never do this because violating privacy goes against the core of my beliefs, but there is a conflict I can't seem to work out. On the one hand, I KNOW that the vast majority of users prefer to sell their privacy than pay…
Even though many people assume it's this way, this choice hardly ever happens in practice. You allude to this yourself. In reality, the choices are usually between paying for something and they still sell your data, and getting it free and they really sell your data.
The majority of paid services have privacy policies, terms of service and user agreements that spell out how they sell data just as much. At best, you might expect that they are a bit more selective in who they sell to, since they're not as desperate for cash flow. However the impact to you is greater - they now have your credit card, address, full name, phone number (all vulnerable to hacks and leaks) and it's harder to lie about these things than with a free account. So the data they collect is more valuable, hence the temptation is higher as well.
Moreover, the paid services have consumer-hostile subscription systems rife with dark patterns. It's needlessly tedious to cancel a service if you decide you don't like it, and even free trials demand a credit card.
Transparency is very low about what is actually done with your money as well. Many services operate at a loss, and the customer charge is just a fig leaf while the real money comes from investors. Arguably, the paid model is a sham for some companies and their real exit is to collect data for a years and then get bought by some data aggregator. On the other end of the spectrum you have people fishing for suckers with ridiculously inflated prices.
For these reasons the choice of paying money is tainted by lack of trust, it is not just consumers being stingy and entitled. Lack of trust can quickly bog down any market.
I don't really blame the industry here, though. It's a bit like California in 1848 - you can hardly blame people for picking up the gold that's just lying around. The real problem is that we don't have the tools, infrastructure and regulatory frameworks that let users see and control how their data is used. If people really want to sell their data in lieu of payment, then let them. But currently, most users are not aware exactly what data gets collected and how much it is worth - they're not able to rationally decide that paying $5 for an app is better than being mined for $20 worth of your data.