3-5k isn't that much.
I assume your Lead Score field is synced to SFDC. But your real issue is the Apex trigger, so you should discuss this with your SFDC Admin to optimize the code or adjust the code to better handle the situation. For example, do those triggers "need" to be activated on lead score?
You won't be able to do a controlled batch unless you use Talend.
The apex fail doesn't necessarily mean the lead data didn't sync, so a re-sync isn't likely necessary. Marketo will auto re-attempt a fix later on anyway.
This is a Salesforce issue. Its triggers need to be bulkified and be able to prevent unintended recursion. If you are using process builder, make sure that:
If Process Builder Queries do not appear to be bulkified as expected in your org, contact Support to verify the permission "Enable query optimization in bulk mode" is enabled for your org.
Happy to have someone here take a look at your trigger code and provide feedback on it.
Thanks Ben, we do have that enabled (as of newest release you can enable on your own in critical updates). I will look into the Salesforce trigger code and see if we can add some filters on there.