"My parents are from Tokyo."
ご両親/両親 is similar to usage of お父さん/父 and お母さん/母. You are respectful to your parents and use お父さん/お母さん when talking to them but use 父/母 when talking about them to someone else. It's not polite to use honorifics when talking about your own "in-group" with someone else.
When using honorific speech you should use honorifics when referring to the listener and their group but use humble speech when referring to your own actions or group. Since ご is an honorific prefix you only use it when talking about someone else's family, not yours.
No, に would not work here.
に shows the location of something when used with a verb of existence like "arimasu" and "imasu".
猫は東京にいます。 (neko wa toukyou ni imasu)
The cat is in Tokyo. (literally: The cat exists in Tokyo.)
In this sentence, "desu" is not a verb of existence and we are not showing where something exists. "Tokyo" is being used kind of like an adjective here to describe the person's origin. In the case of a noun describing another noun like an adjective, it's possible to use the particle の (東京の出身), but you'll find that Japanese often squishes two nouns together to make a compound word, so 東京出身 would be the most natural.
しゅっしん is a bit more posh (because it's Sino-Japanese), while から来ます is the more basic version.
In general, if you have multiple ways of expressing the same thing, kanji-heavy compounds are a fancier way of saying it than words in kana, though in some cases the kanji (even in spoken language) can be helpful in distinguishing between synonyms. In this case, 出身 indicates your origin. E.g. the place you were born/raised*, rather than where you physically just came from, which is how から is often used. Both can be used as the English "from".
*also used for school you graduated from, or field you specialized in.
Your problem wasn't leaving off 私の.
The way you put it kind of sounds like your parents own everyone who hails from Japan.. but a little broken.
両親は東京出身です (My) parents originate from Japan.
The 私の is implied, and can be left off.
Not sure when you posted this. Hope this helped.
の indicates possession, so saying りょうしんのとうきょう would mean "my parents' Tokyo". に is not the correct particle to use with しゅっしん.
One way that you could change the word order around would be りょうしんのしゅっしんはとうきょうです (ryoushin no shusshin wa toukyou desu), which is maybe what you were going for?
The progress quiz is designed to test your progress in the material covered in the whole course. It is a measure of how far you have to go still in mastering the material Duo offers. If you just want to review things you've already learned you can use the practice feature on the main course page or do a checkpoint quiz.