Где и как хранить языковые фразы для javascript в Битрикс?

Все намного проще оказалось.
Регистрируем скрипты через CJSCore::RegisterExt, там же можно указать файл локализации

Я так делаю в шаблоне:

<script>
  BX.message({
    'BTN_MESSAGE_BASKET_REDIRECT': '<?=GetMessageJS("BTN_MESSAGE_BASKET_REDIRECT")?>',
    'BTN_MESSAGE_CLOSE_POPUP': '<?=GetMessageJS("BTN_MESSAGE_CLOSE_POPUP")?>',
    'CART_CAPTION_ADD': '<?=GetMessageJS("CART_CAPTION_ADD")?>',
    'CART_ADDED_TEMPLATE': '<?=GetMessageJS("CART_ADDED_TEMPLATE")?>'
  });

  console.log(BX.message("CART_CAPTION_ADD"));
</script>

Посмотрите как реализовано в стандартных компонентах, для языковых фраз в js используется BX.message

Так или иначе, задача сводится к тому, чтобы в яваскрипт передать фразу в правильной кодировке.

Это либо подключение */lang_id/*.js файла, внутри которого определены лингвистические фразы в виде значения переменных, либо инлайн-инициализация переменных с лингвистическими фразами, транслируемыми через php.
...либо подгрузка через аякс, но и там сводится к одному из двух.

Подключение файла: готовите файл и подключаете его например таким кодом:

$doc_root= \Bitrix\Main\Application::getDocumentRoot();
$js= __DIR__ . '/lang/'.LANGUAGE_ID.'/js_lang.js';
\Bitrix\Main\Page\Asset::getInstance()
	->addJs( $js . '?x=' . md5( filemtime( $doc_root . $js ) ), true );

Инлайн-инициализация при сборке страницы:

<script ...>
lang_me= {
	'MENU_TITLE' : 'php-код'
	...
}
</script>

где php-код:
<?=GetMessageJS('MENU_TITLE')?>
Ныряя в GetMessageJS видим обычный GetMessage, обёрнутый escape-функцией (CUtil::JSEscape) для корректной трансляции символов.