If the workflows are not drastically different, you can achieve 'site-specific' workflow via content security.
Step 1: Workflow security
Create a single workflow definition with some generic access roles for each state. Use these only to grant access to the workflow states.
Step 2: Content security
Create a security role for each site and assign it to where the content lives (e.g. sitecore\content\site1, sitecore\content\site2).
Step 3: Winning!
The Workbox and workflow in general take both workflow state access and content security into account. Users will only see items in the workbox that they have access to for both workflow and content, so users in the same workflow from Site 2 won't see items from Site 1 because they don't have permission to the content in Site 1.
Step 4: Advanced Ninja
You might want to do alternate steps for some sites. Maybe a 'approve with business' state that only Site 1 uses. In this case, using actions and state security that require a specific role will allow you to create users for one site that have access to this action while other sites use a different approve action. This allows you to simulate multiple flows within a single workflow state definition.
You can also have completely separate workflow definitions and create site-specific templates which use different workflows. Suppose you have a 'content page' that is the same in every way between Site 1 and Site 2, but you want different workflows. You create a Site 1 content page template and a Site 2 content page template which inherit all the common presentation details and fields, however you change the default workflow on the site-specific template.
You'll have to play with insert options in this case to restrict which templates are used for which sites. Insert Option rules in the rules engine will help you with this.
Update based on edited question
Handling scenarios when the workbox is too full
If a user is looking for specific content, the workbox is not the place to do it. The workbox works well for teams who are keeping on top of their content. If you have 1000 items that need to be reviewed, then the Workbox just won't work for you. What if those 1000 items are in the site and language that the user needs to find their particular page? No amount of security or configuration will help that.
Instead, I usually suggest using the Gutters in the Content Editor. That way, you can just expand areas of the site and look for the correct icon. I have a quick 25 second video for turning on gutter icons available: https://www.youtube.com/watch?v=IkqG3OnTSvA
In this way, a user can make a more granular search for what they want and take action on the item.