I can't upload a patch because, as the error says:
A patch version cannot contain any new components. The list below indicates which components you must remove before proceeding with the upload.
The problem, however, is that I can't remove the deprecated components. How am I supposed to resolve this issue?
You simply can't do that on a patch. Patches are designed to fix bugs, and therefore you can only touch code, not metadata.
From the documentation (note that the word "added", in most cases, also applies to deletions)
Development in a patch development organization is restricted.
The following is a list of caveats:
New package components can’t be added.
Existing package components can’t be deleted.
API and dynamic Apex access controls can’t change for the package.
No deprecation of any Apex code.
No new Apex class relationships, such as extends, can be added.
No new Apex access modifiers, such as virtual or global, can be added.
No new Web services can be added. No new feature dependencies can be added.
If you want to delete the deprecated components, you're going to have to do so in a new version of the package.
Look at some documentation here and here, in the 2nd paragraph
