I think changing location would be the way to go, if it was connected to a 3rd party service.
If you aren’t able to change the location it probably means that product doesn’t have a location to change to. To solve that you’d go to the product page and Edit Locations, and assign a location that you control.
Then go back to the order, change to that location, mark fulfilled.