Da PWM nur mit Timer1 geht
Das ist nicht ganz korrekt - Timer2 im Mega8 kann auch PWM. Der hat zwar nur einen einzigen Ausgang (B.3 = OC2), aber Du verwendest ja in Deinem jetzigen Code auch nur einen Compare-Wert.

...musste ich Timer0 nehmen -> der hat aber nur 8Bit, da ist die geringste Frequenz 4000Hz.
Auch da kann geholfen werden: Wenn Du Timer 0 mit dem maximal möglichen Prescaler von 1024 betreibst, hast Du eine minmale Interrupt-Frequenz von 16.000.000 Hz / (1024 * 256) = ca. 61 Hz.

Mir ist aber noch etwas aufgefallen: Die Frequenz Deines PWM-Signales liegt bei 8-bit-PWM und 16 MHz Taktfrequenz bei etwas über 30 kHz - ist das denn nicht ein wenig hoch? Ich muss allerdings zugeben, bislang noch so gut wie nie etwas mit Schrittmotoren zu tun gehabt zu haben (eher mit fetten 2kW-Anlassermaschinen, die sich aber mit PWM auch hervorragend zähmen lassen )