Firstly Geoffers,

to DJs United.
Feel free to add your own views, thoughts and experiences to any of the existing posts here on DJU, or indeed, start your own posts as you have done here.
You may have tried this already but, try swapping the leads which run from the Karaoke Player, into the mixer. A faulty audio lead can sound distorted in the way that you describe.
Looking at less obvious things to check...some video players have 3 phono/RCA sockets all bunched up next to each other, typically a red, a white and a yellow. If you accidentally get the Red and the White leads mixed up, it doesnt matter too much as these are just the Left and the Right audio outputs of the stereo signal, and no-ones going to be particularly fussed, or even notice. However, if you've accidently connected the yellow connector on the video player into your mixer audio in, this could cause some fun...the yellow is usually a video out signal...
Also check any International settings on the video player - eg: everythings on PAL, rather than NTSC (some units can auto-detect PAL or NTSC formatted media, yet can be forced to play either format into your chosen output eg: "Play this PAL disc, but send it out as NTSC" (or vice versa).
Also...try the video media in another video player if you've got a spare one.
Do you get any interference audible though your mixer when the video player is idle? eg: not playing - just "ready"? or do you get interference all the time?
Also check for localised interference - I know you mentioned that you've already moved the TV, but try things like (in this weather) any electric fans (the motors can cause interference), multi-way sockets (nice collection of 240volt wiring) etc.
Other than the above, and you own investigative steps that you've tried already, I'm going to have to suggest the strip-down approach...no, no, dont start unbuttoning anything....here goes...
Unplug everything in the room. Even extention leads out of sockets.
Plug the video player straight into a wall socket - all to itself. Unplug all mics or other inputs to the video player.
If the video player has a headphone socket, plug in a pair of headphones and listen for the noise, both before playing a track, and during. anything audible?
Try pluging the video player into a TV (with sound) eg: via a scart or coax lead? any sound problems?
Then try adding the mics back onto the video player (if its got Mic inputs on it)...any nasty noises?
If alls going well up to this point, try pluging the player into your mixer, adding a CD-deck, etc,etc,etc slowly building up to the "normal" system again - noting when (if) the noise appears.
First, have a can of Red Bull, you'll need it after ready all that lot.
Good luck and keep us all informed about how you get on eg: "The noise starts when I...." or "I found out that the humming noise was a trapped wasp....

"....
once again....

Welcome to DJU.