Alterar uma coluna auto_increment existente não parece uma boa ideia - você realmente precisa fazer isso? Em vez disso, por que não apenas modificar sua consulta de seleção para retornar um ID formatado adequadamente? Ao fazer isso, você mantém a integridade referencial e também pode alterar o formato do ID do pedido a qualquer momento no futuro, sem precisar atualizar seu banco de dados.
SELECT id, CONCAT('A2', LPAD(id, 4, '0')) AS order_id FROM <table>;
Saída de exemplo:
+------+----------+
| id | order_id |
+------+----------+
| 1 | A20001 |
| 2 | A20002
...
| 999 | A20999 |
| 1000 | A21000 |
| 1001 | A21001 |
+------+----------+
