Unless I missed it in my quick read, the motor voltage has not been stated. A common problem with newbees and steppers is to supply the voltage that the motor spec states. Steppers should run on 3 to 6 times their 'rated' voltage. I have not messed with steppers in a long time and I don't recall exactly the technical reasons why the stepper rating is so far below the correct operating voltage, the rating is voltage per phase or per winding or something like that. In any case, a stepper will be very lethargic running at its 'rated' voltage and the proof here is the inability for the stepper to accelerate to keep up with the step stream. Steppers are very slow in any case and certainly should be able to reach the few hundred RPM they are capable of. If your voltage is correct, I would suggest you remove the motor from the machine and try to spin it up on the bench. Even an 'un manly' stepper can reach full speed with zero load

.
Steppers draw full power whether they are moving or not, that is why they hold so well, and as a consequence they are designed (insulation and lubrication temp specs primarily) to run hot . . . that's hot, not warm. Perfectly normal, even if they are not moving. Imagine a skinny old guy with his neck stretched out as far as it will go, holding his breath with his face beet red and his eyes bugging out . . . that's how steppers are all of the time . .

However, they will only get to a certain temp and then just stay there. On the other hand, a normal DC motor under a heavy load (holding up an uncounterweighted Z axis, or otherwise held off of its commanded position for example) will continue to heat more and more until it self destructs, so you do have to pay attention to temp on those motors.