Верно: города Бельцы. Географическое название, выступающее в функции приложения, обычно не склоняется, если внешняя форма названия соответствует форме мн. числа.

Это название можно как склонять, так и не склонять.

См. ответ № 212919 . Подробнее см. в «Письмовнике».

Да, по мнению некоторых лингвистов (например, Н. М. Шанского), слова берег и беречь этимологически связаны друг с другом. 

Слово берег восходит к индоевропейской основе *bherg'hos и имеет соответствия в других индоевропейских языках: ср. нем. Berg 'гора', норв. berg 'гора; горная цепь', исл. bjarg 'скала, утес', арм. berj 'высота', т. е. первоначальное значение этого индоевропейского корня – 'высота, возвышение', затем – 'гора, гористый берег' и – уже в общеславянском языке – 'берег' вообще (ср. в русских говорах гора – 'возвышенный берег', дорога горой – 'по высокому берегу реки').

Слово беречь восходит к общеслав. *bergti, исходное значение которого – 'прятать, укрывать, защищать'.  Этот глагол тоже имеет соответствия в других индоевропейских языках, ср. нем. bergen 'прятать, закрывать'. Ученые предполагают, что он восходит к той самой индоевропейской основе *bherg'hos. Развитие значения, возможно, шло следующим образом: 'гора' > 'убежище' (гора, углубление в горе служили средством защиты, местом, где можно спрятаться).

Следует использовать форму множественного числа.

Нормативными словарями современного русского языка эти слова не зафиксированы. Однако в академическом орфографическом словаре зафиксированы термины типа структу́рно-лингвисти́ческий, структу́рно-организацио́нный и т. п. Авторы словаря так комментируют свое решение:

структу́рно слитно/дефисно/раздельно:

1) пишется через дефис как первая часть сложных прилагательных с суфф., несмотря на подчинительное отношение основ, в сочетании со второй частью – относительным прилагательным, напр.: структурно-аналитический, структурно-организационный, структурно-типологический, структурно-функциональный § 51;

2) пишется раздельно в сочетании со второй частью – качественным прилагательным, напр.: структурно неустойчивый, структурно устойчивый, структурно сходный § 51;

3) пишется раздельно с прилагательным-причастием, напр.: структурно детерминированный, структурно оформленный, структурно расчлененный, структурно связанный, структурно упорядоченный § 51.  

Поэтому, хотя в соответствии с правилом сложные прилагательные, образованные из основ слов, отношение между которыми носит подчинительный характер, пишутся слитно (железнодорожный — от железная дорога, *контрактносубординированный — от контрактная субординация), рекомендуем дефисное написание контрактно-субординированный и структурно-субординированный.

Такой пример не только в словаре Ушакова, но и во многих других толковых словарях. Сочетания по дорогой цене, по дешевой цене зафиксированы как нормативные в «Большом толковом словаре русского языка» С. А. Кузнецова, в «Русском толковом словаре» В. В. Лопатина и Л. Е. Лопатиной; значения «о цене: высокий», «о цене: низкий» зафиксированы у слов дорогой и дешевый в «Толковом словаре русского языка» С. И. Ожегова и Н. Ю. Шведовой... Следует признать, что эти сочетания соответствуют литературной норме (с некоторым оттенком разговорности).

В общих руководствах по правописанию для подобных названий правила нет. Слитное, раздельное, дефисное написание иностранных географических названий подчиняется особым правилам, их называют правилами русской передачи географических названий, и они разные для разных языков или групп языков. Но Вы правы в том, что части иностранных названий по-русски пишутся, как правило (а может быть, и всегда), через дефис. Полагаем, что на эту тенденцию нужно ориентироваться и при написании вымышленных названий. 

В литературном языке правильно: из какого города звоните. Вариант с предлогом с — просторечие, его лучше не употреблять.