Checkout this QuickTip. You can use the method outlined to change strings throughout Connections and other plugins in an update safe way. This includes the the labels you want to change.
There are some template specific string which can only be changed in cMap with a few shortcode options. Please see this FAQ. The complete list of str_***** shortcode option can be found on the doc page for cMap. You’ll notice you can even change the labels using shortcode options. If you use those options, they would even override the strings changes that can be done with Say What? in the QuickTip.
Hope that helps!