hallo,
ich bin mir sehr sicher, dass dein Roboterverhalten sogar schon auf einem Arduino Uno proammiert werde kann (2 kB Programmspeicher), wenigstens aber auf einem Arduino Mega mit 8kB Speicher.
Vom Due raten die Adafruit-Leute ja selber nur ab, wenn man mehrere Shields davon aufeinander stapeln will ("Tested compatible with Arduino UNO, Leonardo, ADK/Mega R3, Diecimila & Duemilanove. Works with Due with 3.3v logic jumper. As of Arduino 1.5.6-r2 BETA, there is a bug in the Due Wire library that prevents multiple Motor Shields from working properly with the Due!" )
Ansonsten sehe ich bei nur 1 Shield noch nicht einmal für den Due ein Hindernis - und ich weiß noch nichtmal sicher, ob der Wire-Bug eventuell nicht inzwischen sogar schon gefixt sein könnte.
Das Adafruit Motorshiled hat L293D Motortreiber, damit kann man 2 Motore bis etwa je 600mA betreiben. Ob deine Motore dafür leistungsmäßig geeignet sind, musst du im Datenblatt nachlesen, ansonsten spricht nichts dagegen.

- - - Aktualisiert - - -

P.S., zur von Adafruit erwähnten Arduino IDE 1.5.6-r2 BETA mit dem damaligen Bug:
inzwischen haben wir die Arduino IDE 1.6.12 (habe ich selber) bzw. ganz neu 1.6.13 (habe ich noch nicht selber probiert).
Übrigens, die Arduinos werden schon ewig mit C++ programmiert, das ist villeicht nicht ganz so kompakt wie einfaches C, aber fast - schon die Arduino Unos sind mit ihren Compilern dafür konzipiert, und das passt schon
- nur wenn die Programme irgendwann wirklich anspruchsvoller werden (gefahrenen Weg merken und ein bestimtes Ziel exakt berechnet ansteuern), dann empfiehlt sich eher ein Mega oder Due . Und sogar den hast du ja schon.