La condición del if nunca va a ser cierta. Las variables previousMillis y currentMillis siempre valdrán cero. Y cero menos cero es no es mayor o igual que interval, que vale 500.
Falta asignar el valor de millis() a currentMillis al principio del loop(). Justo antes del if.
Otro detalle: recomiendo declarar interval de tipo unsigned long. Si no se hace así, nunca podrá tener un valor superior a 65535, con lo que "hará cosara raras" si se quieren intervalos de más de 65.535 segundos. También recomiendo poner el sufijo UL a los números que representan milosegundos, para que el compilador los interprete como unsigned long y no los "trunque".
//millis() con L298N y AccelStepper
#include <AccelStepper.h>
AccelStepper stepper = AccelStepper(4, 8, 9, 10, 11);
unsigned long interval=500UL; // El sufijo UL le indica al compilador que el número es un unsigned long
unsigned long previousMillis=0;
unsigned long currentMillis = 0;
void setup(){
stepper.setMaxSpeed(1000);
}
void loop(){
currentMillis = millis();
if ((unsigned long)(currentMillis - previousMillis) >= interval) {
stepper.setSpeed(250);
stepper.runSpeed();
previousMillis = millis();
}
}