I probably should have worded my question differently: How did Israel end up in exile, or maybe more to the point, if not works, than on what basis did Israel receive the Covenant curses?
You have gone too far into the future from Sinai. According to Hebrews 3-4 Israel did not enter rest in the promised land to begin with. Why? Because of disobedience in the wilderness at Kadesh Barnea. Nevertheless the book of Numbers makes provisions for life in the land and Deuteronomy renews the covenant with the next generation. Moreover, whilst in the land they repeatedly suffered oppression for disobedience, and then their own kings were the means of oppressing them. Finally came the exile, but then there was a return from exile. The curses looked forward to restoration in grace. A republished covenant of works cannot deal with this element.
Concerning Galatians 3, a new covenant could not have been added to the covenant made with Abraham, for, as Hebrews 8-10 teaches, the establishing of a new covenant makes the previous covenant old. The argument that Galatians 3 is referring to the law as a covenant nullifies the apostle's argument that the covenant made with Abraham remained in force even under the law.
The apostle expressly states that the law was added to the covenant made with Abraham to bind Israel into the faith of Christ; chapter 4 elaborates that the legal administration was owing to the children being in their minority, but it emphasises the relation of Israel under the law was as children.
Galatians 4 sets up an allegory in which the law is viewed as a covenant of works, but this covenant was established by unbelieving Israel turning the law into a covenant of works. This is Jerusalem below, who is enslaved. True Israel was and always shall be under the covenant of grace of God's making. This is Jerusalem above, who is free.