Just a quick behind-the-scenes tidbit here: Drupal Commerce separates out its internal Order ID from what you see on the front end as the Order number. The Order ID is a serial numeric value that increments with each order created (including orders that are still shopping carts). The Order number can be any alphanumeric string, but it initializes to be the same as the Order ID. (Some sites then update orders upon creation to use a special alphanumeric order number format instead of the regular integer format.)
What you want to change is the AUTO_INCREMENT value on the commerce_order table. This will make it so the next created Order ID will start with the increased AUTO_INCREMENT value. By default when you create a new site, this will be set to 1, but feel free to set it as high as you need it to go. This is especially important if you're migrating an old site but using the same payment gateway, as they sometimes don't support the same order number being used twice.
The query to update this is:
ALTER TABLE `commerce_order` AUTO_INCREMENT = 1000;
Where 1000 is replaced by whatever number you need the next created order to start at. This won't affect any existing order, just the next order to be saved to the database.