The exact same problem gave a little headache for us too.. It turns out the clue is in the message itself: Magento cannot find a shipping method for this order. Maybe you do have some shipping methods configured but for this specific order none works.
In our Magento we have the “Table rates” shipping method configured as “# vs. Destination” and so when we try to make an order with a destination that’s not on the list we receive this error.
Probably best way to check if you have the same problem is to activate “Free shipping” and try again.
Then, check in detail all your shipping method configurations and make sure there is at least 1 configuration that works for your order.