You have to be switched to one side of the KVM, start up that computer and wait for Windows to finish booting. You can then switch to the other computer, power it on, and wait for it to finish booting.
I'm not 100% sure why this is - it's something to do with the video card needing to receive the EDID of the monitor. This is the case on eight different KVMs we have here.