I was under the impression that one of the reasons to mark components (such as Custom Labels) as protected is so they can be removed from a Managed Package with little to no fuss as they can't be depended on in unmanaged code. See SF Docs
I tried to remove a Custom Label from our package as it was protected but packaging failed with the error:
Can't create package version. Removing metadata components from a second-generation managed package is a pilot feature that requires acceptance into a pilot program
So I'm guessing it's only a 1GP feature with protected components and in order to delete even protected components you've gotta be in this Beta Program. Seems it's only possible to "Mark Deprecated" for Custom Labels too. Just not sure I see the benefits of using protected labels in 2GP then if their biggest advantage of being able to delete them isn't possible.