Since K2Store 3.7.x, check address fields are rendered via the Custom Fields manager.
If you wanted to translate the Address field labels, you can enter your translation in the respective fields.
Go to Joomla admin -> K2Store -> Set up -> Custom Fields
Open the field, the label of which you want to change, and enter your translation in the label field.
if you are running multi-lingual site, you can enter a language constant in the label field.
Then you can go to Language manager and create an Override
IMPORTANT: Set the Filter to Administrator before you create an override.
Language Constant: K2STORE_MY_FIELD_NAME
Text: Your translation
Check the For Both locations
You can repeat this steps for your second, third, and other languages.
You can use language strings in all the fields including Custom Error message, Option Titles (if field type is select, radio, checkbox).