TL;DR
You can't put lipstick on a pig and expect it to be the belle of the ball. When faced with a process impediment that can't be changed, such as the one you're describing, you must make the process issues a visible cost to the project. As you have almost no control over the impediment and can do little to control for it, your key goal should be transparency.
Make your process visible and transparent to the team, your stakeholders, management, and the client. It is then up to them to identify the value (or lack thereof) in external processes. Your internal process will clearly identify the value that's being added by the team, and the lead time and process overhead added by any externalities.
It is senior management's job to control for (or accept) process externalities. As long as everyone keeps that in mind, things will run much more smoothly.
Externalize the UAT Feedback Loop
Naturally, this results in many failures reported by UAT, and the items get rejected and sent back to development.
This is a problem, but it is an externality. You have an external process that is adding process overhead (and therefore costs) to your bottom line. The correct way to handle this is to make those costs visible to the stakeholders.
In your specific case, I would remove UAT from the Definition of Done. Work is completed for the Sprint when it passes unit testing, continuous integration, peer review, and whatever else is in your Definition of Done, and then presented as a completed increment to the customer at the end of the Sprint.
They can then spend your next Sprint performing as much or as little UAT as they like while you work on the next increment, and any problems them uncover goes onto the Product Backlog as new work for a future Sprint. This additional lead time will be a visible artifact of their chosen process, and therefore has great merit. This is really the right way to handle this situation, and is a central tenet of iterative development models.
Extend Sprint for UAT with Visible Costs
As an alternative, you can simply extend your current Sprint length by two or more weeks to accomodate their UAT cycle. Part of your Definition of Done will be passing the mid-Sprint product to UAT, and then waiting for the results to come back.
The cost of idle developer time is imposed by the external process. Your job isn't to create busy work, or to perpetuate the "100% utilization fallacy." The team can use that week to update the CI server, patch workstations, do in-service training, or just read a good book. The point is that this UAT cycle has a development cost (whether in non-product work or in iterative work) that is part of the organizational framework. Just make that cost fully visible.
The main risk to this approach is that when UAT is completed, any changes or new work may not have been accounted for in the team's estimates. As a result, you may or may not have enough time to address the changes or rework within the Sprint. As a result, the visible cost to the project will be more failed Sprints (e.g. Sprints that don't meet the Sprint Goal), incomplete work which must then be returned to the Product Backlog, or Early Termination with a return to Sprint Planning.
These are acceptable outcomes in the sense that they ensure that the process remains transparent, and that the cost to the project for these processes is visible to the team, the stakeholders, and the client. Just remember that transparency is the core goal, and that there should never be any invisible work, ever.