That's a fair point, that the Christians to whom Paul was writing would mainly have been Gentiles who would never had been literally circumcised in the first place. They had, however, been spiritually circumcised in their hearts, which meant they were alive in Christ, their sins forgiven. This does make Paul's statement in Colossians 2:13 seem a bit odd, about "being dead in your sins and the uncircumcision of your flesh" (A.V.).
This is where knowing the background to why Paul wrote this letter brings clarity. As the NIV Study Bible preface to Colossians states:
"Paul never explicitly describes the false teaching he opposes in the
Colossian letter. The nature of the heresy must be inferred from
statements he made in opposition to the false teachers. An analysis of
his refutation suggests that the heresy was diverse in nature. 1.
Ceremonialism. It held to strict rules about the kinds of permissible food and drink, religious festivals (2:16-17) and
circumcision (2:11; 3:11)." [Bold, my emphasis]
Other false teachings Paul seems to have dealt with were Asceticism, Angel worship, Deprecation of Christ, Gnosticism, and reliance on human wisdom and tradition.
Paul and Barnabas dealt with the threat of promoters of circumcision trying to get Gentile believers in Christ circumcised in Acts chapter 15. This threat persisted for some time, so that it would be no surprise if Paul had to write to the Gentiles in Colossae about the trap of being circumcised in the flesh. If that is taken as understood, then what he says in the verse in question makes more sense.
Although they may not have had that circumcision, they might yet submit to the knife if those false teachers could persuade them. Paul therefore set out the case for the futility of physical circumcision, which never took sin away, adding that they had already had their sin taken away due to that spiritual circumcision of their hearts. To put it in modern parlance, "It's a no-brainer. You've already been made alive when forgiven due to God 'blotting out the handwriting of ordinances that was against us, which was contrary to us, and took it out of the way, nailing it to the cross' (vs.14). Why on earth would you then think physical circumcision could either improve on that, or add to that?"
Here is how Matthew Henry expresses his view of verse 13 in his Commentary, in the language of his day, over 300 years ago:
"It is principally to be understood of the Gentile world, who lay in
wickedness: they were dead in the uncircumcision of their flesh,
being aliens to the covenant of promise, and without God in the
world Eph. 2:11, 12. By reason of their uncircumcision they were dead
in their sins. It may be understood of the spiritual uncircumcision
or corruption of nature; and so it shows that we are dead in law, and
dead in state. Dead in law, as a condemned malefactor is called a dead
man because he is under a sentence of death; so sinners by the guilt
of sin are under the sentence of the law and condemned already. Jn.
3:18 and dead in state by reason of the uncircumcision of our flesh.
An unsanctified heart is called an uncircumcised heart; this is our
state. Now through Christ we, who were dead in sins, are quickened
[made alive] together with him -by virtue of our union to him, and in
conformity to him. Christ's death was the death of our sins; Christ's
resurrection is the quickening of our souls." Page 1869
Conclusion: They were dead in sin when they were uncircumcised, and they would remain dead in sin if they became circumcised. The only thing that could take their sin away was that miracle of grace, being given a new, clean heart that now beat for Christ. And that had already happened! Job done! Rejoice in now being out of the shadows by being united to the reality, Christ, by faith.
