So, the error being returned from paypal is "Security header is not valid":
<LongMessage xsi:type="xs:string">Security header is not valid</LongMessage>
This error means there is an issue with the API Credentials you are supplying.
Double check that you are using Valid API Username, API Password and API Signature value.
This can also happen if you set the cart to use the sandbox and are using live api information or vie versa.
Before using the API Information, PayPal requires that you accept the billing agreement. If you have not accepted the billing agreement, you may get this error.
If you are positive that you are using valid API Information, try requesting new api credentials, sometimes the API credentials are just bad.