One additional thing to add to the excellent answers already given is that -stan is actually used productively in Persian for other words as well, such as bimarestan (بیمارستان) for “hospital” — literally “land of patients”. Or gulestan (گلستات) for “garden” — literally “land of the flowers.”

So no matter what the historical record shows about the first recorded instance of a particular place name, the fact that it's a productive suffix to begin with suggests that any Persian-speaker (or Persian-influenced speaker) could form these sorts of names on the fly, whenever s/he wanted to.

No, the terms are not all contemporary. Afghanistan is recorded in the 13th century; some of the others appear to date to the 20th century. Pakistan is 1933, the others probably date from either the Soviet federation or independence in 1991

Also note hat tip to @jamesqf that Balochistan is a -stan predating Pakistan, therefore not all the -stans appeared simultaneously. I can't find a clear date for the first use of the name Balochistan, but it is earlier than Pakistan.

Below I've provided superficial answers to what seemed to be the core of the original question. I'm not clear on the scope of the ancillary questions, but the sources provided should provide a starting point for further research. Note that in several cases it isn't clear whether the term refers to a state (OP specifies a "sovereign state") vs a subordinate political unit or a culture area

Afghanistan

13th century

The earliest mention of the term "Afghanistan" appears in the 13th century in Tarikh nama-i-Herat of Sayf ibn Muhammad ibn Yaqub al-Herawi, mentioning it as a country between Khorasan and Hind, paying tributes to the country of Shamsuddin.[19] Wikipedia:Afghanistan

Kazhakstan

1962

See The So-Called Virgin Lands of Kazakhstan 1962 hat tip to @jan

Kazakhstan was the last of the Soviet republics to declare independence during the dissolution of the Soviet Union in 1991. Wikipedia:Kazhakstan A more complete treatment can be found in Wikipedia:KazakhSovietSocialistRepublic

hat tip to @default-locale with minor edits "Kazakhstan" was supposedly mentioned in XVI century work by Zainuddin Mahmood Wasifi (source in Russian, (no English translation available)). Both "Kazakhstan" and "Uzbekistan" were widely used in the early XX century. For example, the newspaper was renamed to "Socialistic Qazaqstan" in 1932 and "Uzbekistan" was mentioned in 1928 magazine.

Pakistan

1933

The name of the country was coined in 1933 by Choudhry Rahmat Ali, a Pakistan Movement activist, who published it in a pamphlet Now or Never, using it as an acronym ("thirty million Muslim brethren who live in PAKISTAN"), and referring to the names of the five northern regions of the British Raj: Punjab, Afghania, Kashmir, Sindh, and Baluchistan.[26] Wikipedia:Pakistan

Tajikistan

1924

Tajikistan has existed as a state only since the Soviet Union decreed its existence in 1924.StateUniversity.com

Turkmenistan

1956

See Soviet Turkmenistan, a work from 1956 hat tip @jan

The name Turkmenistan is derived from Persian, meaning "land of the Turkmen". Before 1991, it was a constituent republic of the Soviet Union, called the Turkmen Soviet Socialist Republic. mcgill.ca

Uzbekistan

1991

During the Soviet era Uzbekistan was the equivalent of an American state known as the Uzbek Soviet Republic. It became Uzbekistan after independence in 1991. FactsAndDetails

The Persian suffix stān is much older than any of the “stans” in modern Central Asia. It goes back to proto-Indo-Iranian as represented by Sanskrit sthāna- “standing place” (already in the Rigveda) and Old Persian stāna- with the same meaning. In early New Persian (texts from the 10th century AD onwards) we have names like Turkistān “land of the Turks”, Čīnistān “China”, Hindūstān “India” and many others. These names are all well known in the Persianate cultures of Central Asia and India, where -stān becomes a productive suffix for forming names of countries, even countries as far distant as Lehistan (the Turkish name for Poland).