Do you have or can you get the torque specs on the present motor. That would give you a starting point for choosing the motor. Once you have a motor chosen, then choose an appropriate stepper motor driver. The motor shield might be OK but specialized stepper drivers will be more efficient and have features that are not present with the shield.
Stepper motor basics might have information of interest.