On 13 May 2014, Starostzik signed with 3. Liga side Stuttgarter Kickers. He broke into a starting role in his first season, making 25 appearances, 24 of which were starts and added one goal. Starostzik helped Kickers earn a fourth-place finish in the 3. Liga that season, one spot short of the promotion play-off. Starostzik continued to be a regular presence on the Kickers backline in the 2015–16 season, making 28 appearances, however the year ended poorly as the club was narrowly relegated by goals for after tying with Werder Bremen II on points and goal difference.
In May 2016, Starostzik signed with newly-promoted 2. Bundesliga side Dynamo Dresden. On 18 December 2016, he made his 2. Bundesliga debut as an 84th-minute substitute in a 1–2 win over Arminia Bielefeld. He went on to make a total of only four appearances that season, including two starts.
Frustrated with his lack of playing time in Dresden, Starostzik returned to the 3. Liga in July 2017, signing with Hallescher FC. He appeared in 15 of Halle's first 16 matches of the season, including 14 starts, before suffering an injury in a match against Preußen Münster on 17 November 2017. After recovering from his injury, Starostzik saw almost no playing time for the rest of the season, except for one appearance in the Saxony-Anhalt Cup against 1. FC Magdeburg in March 2018. This treatment persisted into the 2018–19 season as Starostzik was not even named to the club's 18 for the entire first half of the season, and as a result Starostzik asked to leave the club to pursue other opportunities during the 2018–19 winter transfer window.
On 7 March 2019, Starostzik signed with Canadian Premier League side Pacific FC. On 28 April 2019, Starostzik scored Pacific FC’s first goal in history, in their inaugural game. The match ended in a 1–0 victory over HFX Wanderers FC. Starostzik’s goal was the first header in Canadian Premier League history, as well as the first goal by a foreigner. On 4 November 2019, the club announced that Starostzik would not be offered a contract for the following season.
