We had (have) discovery, auto-scaling and redundancy in PaaS. Most apps could run just fine in Cloud Foundry/App Engine/Beanstalk/Heroku. But the devs insist on MongoDB & Jenkins instead of using the cloud-provider solution and now you're back to defining VPCs, scaling policies, storage and whatnot.
Cloud foundry has been my best experience with enterprise cloud so far.
The issue was mainly with the admins not provisioning enough capacity, but for us devs it was fucking magical.
But as of where we are now, it is a good abstraction to get there. It provides a lot of stuff like service discovery, auto-scaling and redundancy. Yes you do need to have instances to run K8s, but that is as of date the only abstraction that we have on all cloud providers, local virtualization, and bare metal. So yes it isn't true on demand "cloud" but in order to work like that you need to fit into your service provider's framework and accept limitations on container size, runtime, deal with warm up times occasionally.