In another exercise, "Elle s'est partie seule en lune de miel," en replaced pour sa (pour leur, here). Seems inconsistent not to accept the same here.
Not really. "En lune de miel" is the destination of "partir". In this sentence "au Québec" is the destination of "aller".
Is it wrong to use "elles sont parties au Québec pour leur lune de miel" ?
That would mean "They left [...]", not "They went [...]".
Why isn't it à Québec similar to à Paris, à Berlin or à Chicago?
It's a province. The others are cities. À Québec would Quebec City, though the city and capital of the province is often called Ville de Québec.
Has to be au Québec. The various provinces of Canada have different genders so it is 'à la Nouvelle Écosse' and 'au Québec' for example. The attribution of the genders of these provinces is entirely arbitrary!
"À Québec" is accepted. Nowadays at least.
What's wrong with "ils sont" ?
Ils sont allés is accepted. Note that it requires allés but elles needs allées.
Why elles not ils?
Ils still rejected as of Feb 14 2021.
It's accepted, you probably forgot to make the participle agree.