Yes! My VPS provider uses KVM (Kernel-based Virtual Machine) as their virtualising system and I have no problem using MT4 or MT5 on it.
I am currently using Windows 2008 R2 Server as my base OS in all my MetaTrader VPS setups, but it will work just fine on the newer Windows versions as well.
KVM is the underlying virtualisation system being used. It has nothing to do with the Operating System selected for the VPS.
However, MetaTrader is a Windows application, so it is best to use a Windows OS. You could use a Linux OS with WINE to simulate the windows environment, but that would be a type of double virtualisation and a waste of resources.
So, stick with a proper Windows OS when selecting a type of VPS to run (not CentOS, Debian, Ubuntu).