You can run them on the same box just fine. There's nothing magical about any of those processes.
However, using dedicated masters (by which I mean mostly kube-apiserver) separate from worker nodes is a good idea to avoid high load impacting the API access.
(Just keep in mind that the Kismatic packages I referred to won't support this — you can't install kubernetes-master and kubernetes-node at the same time. But as you discovered, you can run everything except kubelet as pods. On the other hand, kube-apiserver needs a whole bunch of mounts as well as host networking, so to me it seems like you don't gain all that much.)
What is this Docker key-value store you mention?