Hi,
Like any text in HikaShop, you can edit your translation file via the interface in the languages tab of the config and override the translation.
However, the "New" text is a generic text which is used in a lot of places. If you change it to "Add a new address", that will change it everywhere which is not what you want.
So you need to edit the file address_view of the view checkout via the menu Display->Views and change directly the code JText::_('HIKA_NEW') by your text "Add a new address" so that it is replaced only there.