Driving high current bipolar stepper motor with high voltage
One possible solution to this is to use two L298 DUAL FULL-BRIDGE DRIVER ICs wired in parallel. For instructions on the correct way to do this, refer to "APPLICATIONS OF MONOLITHIC BRIDGE DRIVERS" page 2, the section titled "PARALLELING OUTPUTS". The L298 will allow supply voltages up to 46V and the parallel combination is recommended for stepper motors up to 3.5A

To control the L298, consider using the L297 STEPPER MOTOR CONTROLLER which will handle the chopper-drive control better than you can do with the Arduino.

There are reference schematics in the datasheets and application note referenced above.

You can use your Arduino to handle the step and direction (/CLOCK and CW/CCW) signals to the L297. Be aware that to run your motors at the highest speeds, you will need to ramp-up and ramp-down the step rates in order to accelerate and decelerate the motor. You will also need to limit any "jitter" in the step (clock) timing as much as possible or the motor may slip (lose steps) or not turn at all. This "jitter" is often caused by latency due to other interrupts. This may be improved by keeping interrupt routines short and (even better) giving your stepper motor timer interrupt the highest priority (not sure if that is possible as I have no experience with Arduinos).