Assuming there is no talk of 旅館 beforehand, then in the first conversation you have introduced the topic (旅館) with the first line so yes, you would use は not が when asking if there are 旅館 in Melbourne. But, rather than:
メルボルンに旅館はありますか?
I might have said:
旅館はメルボルンにもありますか?
or even:
メルボルンにもありますか?、旅館は・・
(You might even not have to mention 旅館 at all in the second line, but it all depends on the context, the moment and how obvious the topic is to the other party.)
In your second scenario you are introducing 旅館 in the second line so が would be appropriate.
Edit (after reading the other answers and giving it some thought).
1) In my answer I tried to avoid using には to keep it simple and chose a response using も.
2) The first scenario is easy because the topic has been mentioned. What is harder is explaining why が does not have to be used when 旅館 has not been mentioned. I think one short answer is that:
If you mentioned that you were going to Melbourne and asked about 旅館 because you were looking for somewhere to stay then は can be used because the listener can infer that from the previous statement. (This is admittedly more likely in Kyoto than Melbourne but if we assume its a conversation between two Japanese people it is easier to imagine.)
As mentioned は and が is a complicated subject and different books give different rules. You have cited a beginners text book if you are looking for short explanation, that can be difficult. My notes are below.
"A students guide to Japanese Grammar" by Naomi Hanaoka McGloin gives the following cases when it is not necessary to introduce a theme with が:
(i) Nouns mentioned in previous discourse
(ii) Nouns not mentioned but can be inferred such as エンジン in the following sentence.
先週車を買いました。エンジンは日本製です。
(iii) Nouns that have not been mentioned but can be identified non-linguistically. For example if you hold up a book and say;
これは私の本です。
(iv) Nouns uniquely identifiable such as the River Amazon in the following sentence:
アマゾン川は南アメリカにある。
(v) Generic nouns. For example:
日本人は寿司を食べる
Q: How can we apply these to the second scenario and conclude は is appropriate?
A: If you mentioned that you were going to Melbourne and asked about 旅館 because (for example) you were looking for somewhere to stay, and that was clear to listener then case 2 would apply.
Now, I am not going to argue my first answer is better (I am learner trying to learn from my mistakes and open to correction) but if you wish confirm the existence of something that could not be inferred from the prior conversation then が would be appropriate. To take a more clear cut example, if you wanted to ask if it rained in Melbourne very often then I think you might say:
私はメルボルンに行きます。
メルボルンでは雨がよく降りますか?