Disclaimer: I am not a native English speaker nor an English teacher, rather an advanced learner. The answer below was written primarily based on common sense and the logic of grammar and might contain minor errors.
In your sentence, it is the "states and territories" that imposed restrictions and, presumably, each state or territory did so with respect to their respective residents. Therefore, "their" is the preferable option. You can also see it if you replace "all" with "some" in your example:
Some of the country's states and territories imposed travel restrictions on their residents.
— still makes perfect sense.
Some of the country's states and territories imposed travel restrictions on its residents.
— did the states and territories also somehow restrict residents of other areas? On what grounds?
The context and your desired message are also important here. If the restrictions you are talking about are regional, but implemented in every single region, then you would want to choose your second version. If, however, the restrictions are country-level and apply to each region without exception, then I would suggest rephrasing your first sentence, e.g. as follows:
The country imposed travel restrictions on its residents in every state and territory.
The country imposed travel restrictions on the residents of all its states and territories.