These types of errors are best understood by separating the Okta messages from the service provider message, in this case Salesforce. Typically the colon is the divider between Okta and the SP, so in your case the message would appear as such:
Okta: Failed to provision user due to:
Salesforce: Insufficient access rights on cross-reference id
So it seems that Okta attempted to provision a user ,using the API, into your Salesforce tenant and that job failed (first message). The job failed because Salesforce, instead of creating the user as requested by Okta returned an error, the error stating "insufficient access rights on cross-reference id" (second message).
As to why Salesforce is returning the error to Okta? That interpretation is best left up to Salesforce support, but based on the error it sounds like the user account used for authentication does not have the appreciate access to create users. As such I would verify with your Salesforce admin that the provisioning account has the correct permissions. Perhaps you can login directly to Salesforce with that user account and attempt to create a user , you should see a similar error if this indeed a permissions issues. You can find the account Okta is using by going to Applications>>Salesforce>>Provisioning, it will be noted under the "API Credentials" section.