The major cloud providers' deployments of Kubernetes (and other server-side persistent-orchestrator systems, like the venerable CloudFormation) are deeply integrated into the cloud platform they're running on, such that the orchestrator itself can provision resources for a container to run on as part of deploying the container. This becomes important when elastically auto-scaling a container, because each container might need e.g. its own disk, and you can't create them ahead of time if you don't know how many you'll need.
This also means that, unlike a CaaS, k8s et al can manage the very cluster that k8s is running on, scaling it out to suit the size of the current/estimated workload.
Theoretically, you can bootstrap k8s on top of a vanilla CaaS—this is how minikube installs "using" your local Docker install, and this is how deployable PaaSes like Flynn and Deis work. But this approach doesn't supply k8s with the cloud-specific integration it needs in order to provision stuff. It might work if you're deploying against something with a standardized API like OpenStack; but none of the major cloud providers are compatible with such APIs, and so they need to build their own k8s plugins that call their IaaS-level APIs, to make k8s work on their clouds.
Or, to put all that another way: if there were standard IaaS-level APIs for k8s to hook into, Docker (and the CaaSes that either use or emulate it) would just hook into those APIs itself, and there would be no need for a higher orchestration layer.
Then setup/teardown in specific order.. and if you have state, keep a subset of containers alive to avoid loosing state (even if it's replicated).
For example, a pod that requires a postgresql pod to connect to will fail and crash out. The scheduler will start a new one. If the postgresql pod is up by that point, then the rescheduled pod will no longer crash.
As far as the network paths, one of the really cool things about pods running inside a k8s cluster is that they can access any of the other pods, even if they are on a different node. However, pods typically reference services (such as postgresql) by dns name. You specify the set of pods that belong to the service by label selector. This allows the pods to come up, tear down, crash, moved to another node, while the service maintains a stable point of contact. It is quite brilliant, and other orchestrators quickly tried to copy it.
Stateful workloads are still difficult. Each distributed stateful system has its own way of setup and teardown. What we will probably see are custom Operators designed for each distributed stateful system, coming out over the years.