This problem is partially caused by PayPal. PayPal somehow remembers all of the OrderIDs, so in case you performed some test orders and you have deleted them after and tried to create a new order it might have the same OrderID that has been previously marked in PayPal as "paid".
We suggest you to go to the Kentico CMS database -> COM_Order table and check your 'OrderID' column, eventually to increase next OrderID to some value you are sure has never been used before.
Or, it seems that the email you should use in Kentico for the Paypal integration is a seller account you have to create under Paypal and NOT the email for the entire sandbox.