-- Say, if the private key for that address is stolen, would signing be of any help? (Since Bitcoin is decentralized and no one in control, where can one appeal to to in such a case)?
That's not what signing is for. The purpose of a signed message is to prove that an specific address belongs to you. Let's say that I create an account here at BitcoinTalk and tell everybody that the address 1XXXXXXXXX is mine. If I ever get hacked and lose my account, I can create a new one and post a message signed with my 1XXXXXXXXX address to prove that I'm the original owner of the account.
-- Also, would not the private key be exposed unnecessarily due to the signing? (leaving the paper/cold wallet as it is would be more advisable)?
You don't need internet access to sign a message. If you sign directly from your cold wallet or temporary import your paper wallet in a air-gapped device, your private-key won't be put in risk.