亜米利加【アメリカ】
伊太利亜【イタリア】
独逸【ドイツ】
I know these spellings are rarely used...
My question is: Why did they choose exactly these kanji characters for spelling these countries' names?
Could they use other kanji characters but with same readings for spelling these countries?
General phonetic "rules"
For a lot of words that are now written using Katakana, there was a tiny amount of logic to it. 亜 transcribed ア virtually exclusively, 伊 is a very common kanji for transcribing イ, 加 for カ, 利 for リ, and generally the kanji from which Katakana come is a good rule, though far from perfect (as noted with ア, and in タ which is usually transcribed as 太 (origin of た)) [see image]
In fact, sometimes there aren't even consistent transcriptions for one word. アラビア on my IME gives options of 亜拉毘亜 and 亜剌比亜, and even 阿剌比亞 (using the older version of 亜). Nowadays katakana is standard. The website in the comments section of the main post has a much larger list.
Syllables ending with -n tended to be transcribed by syllable (as opposed to kana). 芬蘭 (フィンランド) is one example of this.
Chinese's Influence
Sometimes the transcription was a derivation of the hanzi used to transcribe something in China. スペイン (西班牙) would by conventional logic be read as "seibanga", with the most common respective readings of the characters being せい、はん、and が. In fact, the origin comes from Chinese, where the word is read as "Xibanya". Much closer to the pronunciation of "España" we're used to! The Japanese word is スペイン, obviously a loan from English, but doesn't match these characters much.
Meaning
Sometimes a fair few characters are possibilities, and the one chosen doesn't follow any pattern above. One reason for this was the attempt to still keep Kanji with some semantic (meaning) aspect to the word. フランス、スペイン are both examples of this, with respective characters both containing 西（仏蘭西、西班牙）. This makes the actual transcriptions generally quite messy.
Other notes
There are non-country names that got given kanji to transcribe sounds too, including 缶{かん}, which was obsolete by the time the Dutch arrived in Japan, so was revived to mean "can". 亜細亜 is common for "Asia" on wartime post stamps. 煙草{たばこ} is common, even today, in place of katakana for "tobacco" (both chosen because of meaning purely, and have 0 phonetic relation to the word).
It's not common to write out entire words like this anymore, with katakana largely replacing it. You'll see it every now and again, but much more commonly these characters are still in frequent use in newspapers as contractions of country names to keep headlines short. Headlines such as
独、伊決勝へ！"Germany and Italy advance to the finals" (say, in soccer)
米国大統領来日 "American President Comes to Japan" (all kanji)
are in the newspaper I have in front of me right now, for example.
Why did they choose exactly these kanji characters for spelling these countries' names?
It's hard to tell exactly why, because these are mixture of various transliterations done by Japanese and Chinese (of course different between Mandarin or Cantonese or other dialects) speakers that happened to hear the sound for the first time.
For example, there are some old school members which have been known for a long time in fixed Chinese characters: 蒙古{モンゴル}, 西蔵{チベット}, 印度{インド}, 越南{ベトナム}, 希臘{ギリシャ} (funnily the kanji are from endonym Hellada but the reading is from Portuguese Grécia), 埃及{エジプト} etc.
Modern (somewhat) systematic namings tend to choose those simple but not-everyday-used characters: 伊 ("yond"), 亜 ("minor"), 尼 ("nun") etc.; or those euphonious: 英 ("bright"), 利 ("advantage"), 蘭 ("orchid") etc. But there are still many possible options. As you can see in the WP page in @snailboat's comment above, there once was much more arbitrary transliterations, most of which have been gradually thinned down by now.
Some other factors can influence kanji choice, too. 葡萄牙{ポルトガル} is thought to contain 葡萄 ("grape") because its main export to Asia was wine. ロシア was originally spelled 魯西亜 instead of 露西亜 until Russian embassy made a complaint that 魯 could mean "obtuse".
Could they use other kanji characters but with same readings for spelling these countries?
As for this, definitely no. They are already recognized as proper names that you couldn't change them as you wish.
On 独逸 the kanji choice for Germany. It is not phonetic but ideological and deliberately anti-German. This is in accord with the Chinese/East Asian 華夷思想 Huáyí Sīxiăng (J. Kai Shisô):Thought that the own culture is superior and contempt of others regarded as 夷 ‘retarded Uncivilized’ or ‘animals’ (and insects) below human beings (also 中華思想 Zhōnghuá Sīxiăng (J. Chûka Shisô): Superior Land In The Middle Ideology). Including the 犭 beast classifier here is not just the otherwise often relatively harmless pride for the culture of one’s own realm, but the deliberate despite of others as beasts. Understanding this is a matter of study of East Asian thought. As this is quite embarrassing, Japanese will usually avoid admitting this. Certainly, diplomats of the German-speaking countries and their counterparts should work towards a decent naming.
> at the beginning of the quoted line to clearly indicate citations.