It is possible for PayPal to report an order as already being paid if they have received an identical invoice number in the past. This usually occurs if the merchant uses the same PayPal account on multiple stores, and eventually, a previously issued invoice number sequence is sent from the second store.
There are two separate options you can use to resolve this issue:
In Your PayPal Account:
Login to your PayPal account by going to www.PayPal.com.
Click Profile on the top menu bar.
Under "Selling Preferences," click Payment Receiving Preferences.
Under "Block Accidental Payments," choose No, allow multiple payments per invoice ID.
In Your Shift4Shop Account:
Log into your Shift4Shop Online Store Manager
Go to Settings > General > Store Settings.
Click on the Checkout tab and look for the Invoice Number portion of the page to click on Edit Invoice Number.
Increase the invoice number so that it surpasses the last invoice number received by PayPal, and click Save Changes.