Anything with decent physical resistance (10%+) - Guardsmen, Horsemen, Orc Veterans (their counterattack ability is great), Demons, Executioners, Archdemons, and such. All of K'Tahu attacks are physical based. Having no knights will prove to be a problem though... Still, nothing 2x Stone skin can't fix.
Try playing with Paladins hitting his armored side (armored hand) and one other unit with good damage on his weak spot. This will give you 2 units hacking at him and 3 mopping up his summons.
That is, assuming you want to win the fight with minimal losses
