If the paid for search engine ignores SEO "optimizations" and actually ranks on content AND these results prove better that attracts actual paying users, then we don't have to wait for SEO to die. Just like SEO rose to prominence to win Google result ranking because that's where the users were, the sites would stop the SEO crap.
Getting this hypothetical site to get users is the real problem. Same thing with getting users to a Facebook alternative.
So having a paid search engine does not fully solve the SEO problem. Having no Ads does not takeout the SEO problem of boosting pages to top.