You might just want a lower current wall wart. The Arduino analogWrite will change your average current, but it will more directly change your voltage. So if you need a 12v power supply for the stepper, the PWM from Arduino will drop the voltage and give your problems with the stepper. Or you could build a current limiting circuit on your device, but that will probably also get hot. If you're just testing and you have no other power supply, try hooking up a few other devices to your supply to drop the current.
This is incorrect due to a common misconception of power supply ratings. The actual current in a circuit is determined by the resistance (or reactance with AC circuits) for a given voltage level. The 12V 8A supply in question will not force 8A, rather it will supply a 12V level as long as the current draw is 8A or less. So you don't need any other devices to "drop the [excess] current". If you try to draw more than 8A many things may happen, among them:
A) a fuse (thermal or otherwise) or breaker will trip cutting the voltage off
B) the supply voltage will drop
C) the supply may melt down in a ball of fire.
Most commercial devices will either be A, or B followed by C. My laboratory grade bench supply at work will do B to maintain the maximum current (set by a dial instead of a rating...)
In the real world, however, there may actually be a minimum
current where the output voltage may not be stable. Unfortunately, this value is rarely if ever given on commercial equipment. I remember building low power computers (anyone ever hear of the AmigaONE computers?) and having to make sure I used low wattage computer power supplies. This was because most of the high wattage computer power supplies didn't regulate the 5VDC and 12VDC lines well with the low power draw of the motherboard.