This isn’t an SDK problem; this sounds like a deployment target problem. NSNotFound-as-defined-in-Swift wasn’t in Foundation in macOS 12; it was (I think) in the separate libswiftFoundation overlay dylib. So whoever compiled swift-package should have set the minimum deployment target to, uh, whatever the minimum is supposed to be.
(Or maybe they did do that. Apple doesn’t usually support more than one OS version back for its Xcodes, maybe the prebuilt Swift toolchains are the same.)