Use Paypal generated Invoice ID for store invoice number

For that you would want to use something like: https://www.woothemes.com/products/sequential-order-numbers-pro/?ref=5&campaign=article

It will allow you to start the order numbers at any number you want.

There may be some other options available, too. I’d do some searching for custom WooCommerce order IDs. You can probably even find a quick hook/snippet to use to customize them yourself real quick.