Holding the button usually makes the timing pretty easy, but it doesn't completely get rid of the need for timing. You still have to be reasonably close to when you would need to input the move, and it doesn't work for normals. If the moves are not coming out at all, you're likely doing the motion and pressing the button too early, or after the cancellable window of the move you're doing beforehand. Without knowing exactly which cancel you're trying to do, it's hard to tell which.
As for Kyo cancelling his DM into Neomax, you have to be in HD mode, and that one requires 3 or 4 bars to do altogether, depending on if you're using his EX DM or regular DM. If you're in HD and have enough meter, you can do that cancel really fast. The motion for his Orochinagi (his DM) is qcb,hcf+P, and his neomax is qcf,qcf+AC. The timing for this isn't too bad. You should start the neomax motion pretty much right away after the DM and hold the AC at the end, it should come out easily enough. You have a decent amount of time in between, so you don't need to rush it. The Neomax will come out almost as soon as the DM hits. Kyo's Neomax can't be done in the air, so this is all on the ground.
King is a great character for new players to start with in my opinion. I have a lot of trouble trying to do Mr. Karate's more complicated stuff like super-jump cancels, but if you can pull that off then that's great, keep doing what you're doing. He's a very good and versatile character. It's a good idea to try out a few and see who best fits your playstyle and who really "clicks" with you in general.