"Application" is one and the same as "CustomApplication" - the metadata is stored in the "applications" folder in SFDX source project structures and with the ".app-meta.xml" extension, but uses the CustomApplication element as the root of the metadata XML.
As you noted, the documentation specifically states that:
Both Package Developer and Subscriber Can Edit
All attributes, except App Name and Show in Lightning Experience (Salesforce Classic only)
All attributes, except Developer Name, Selected Items, and Utility Bar (Lightning Experience only)
When both the package developer and subscriber can edit a value (similar to what happens with page layouts) changes made by the package developer do not get applied during upgrade just in case the subscriber has changed that value. That includes "label" in this case.
I believe, therefore, there's nothing you can do to update the label automatically during upgrade without jumping hoops and using the Apex Metadata API to overwrite that label. Note that using this from a post install script is challenging due to the fact that the running user is the "ghost user", and this fake user has some specific limitations.
Additionally, the whole point here is that the subscriber might have changed the label themselves, so really you should leave it alone. New installs will see the new label, old installs get to see the old one (or subscriber customized value).