This is probably a resolution and/or refresh rate issue.
What is the native resolution of the monitor and are you driving it at the same resolution from the PC and the Mac? I would guess the PC is driving it at its native resolution and 60 Hz, and your Mac is trying to drive it at either higher than native resolution, or at higher than 60 Hz. Open your preferences panel for your display (Hardware, Displays) and verify that you are at the right resolution and the right refresh rate.
If the PC works through the KVM, the KVM is OK, it has to be how the Mac is driving it.