Hi @legor ,
Your best bet is likely to recreate the order in a draft order, mark it as paid, and then from there you can generate a new shipping label. You can cancel the original order (without refunding it) so that your reporting remains accurate.
In terms of recouping the shipping costs, this is likely not possible but if you agree with the customer that they should pay for the second shipment attempt, you can add this additional shipping cost to the new draft order and issue them an invoice.