The complexity of Kubernetes is overstated, so I think they can. However, it doesn't mean they should. Personally I would just start with a docker-compose.yml and run it on a VPS. In the starting phase you probably don't have much traffic anyway and docker-compose can nicely progress to Kubernetes when you need it. Another upside is that any developer can run the entire stack locally on their machine, which a huge upside as well. This means you can fully focus on producing working code and don't have to bother about infrastructure too much.

Then again, I've never worked in a startup so the above approach is purely theoretical. Curious about what other people think.