Not quite sure where you're getting your directions from? The south of Thailand is long and skinny, it's north from Hat Yai to both Bangkok and Krabi.
If you want to go by train, I'd take it as far as either Surat Thani or Trang, and then switch to a bus. Trang is a bit closer (~2 hrs by bus), but it's smaller and less well served by trains, while Surat Thani is further away (3-4 hours) but better connected.
The alternative, which will probably work out faster and more comfortable if you pick your bus well, would be take a direct bus from KL to Hat Yai. It's about 10 hours all in and there's plenty of choice, this site lists a few -- fares start from RM 50, but it's usually worth paying a few bucks extra for a nicer bus. From Hat Yai you can catch another bus to Krabi, travel time ~4 hours.
All that said, I have to agree with WW that the direct Air Asia KUL-KBV flight at just over an hour would be a no-brainer if you didn't insist on land transport...