There is no special "empty space" due to the action of these pumps. Ions are very, very small and even in liquid there are always gaps between molecules/ions/atoms. If you dissolve a bunch of salt in a glass of water, the volume doesn't change noticeably, but even if you measure carefully you find it actually decreases. That's because water molecules surround the ions and take up a bit less space than they would in a pure solution.
Additionally, sodium, potassium, other ions, water, etc. can all cross membranes by a variety of mechanisms. For charged ions, they cross the membrane primarily through ion channels though also through transports, some of which use ion concentration gradients to move other things (see https://en.wikipedia.org/wiki/Cotransporter).
Though flow through these channels is indeed somewhat random, in aggregate you can predict how much ions will move. It isn't as though a random ion will "replace" a sodium ion that has moved, rather, all ions will have net flow according to their concentration gradient and any electrical gradient across the membrane. You can determine the direction of net flow for given ion using the Nernst equation.