It's interesting that you didn't have these issues prior to Xcode 13. Multiple people already had issues with binaries and SPM in Xcode 12.5 and earlier. See here: Headers not found for an XCFramework packaging a static lib for iOS (critical). This thread also contains a link to a Bug report.
Your issue seems to be the same or at least related.
Note, the release notes of Xcode 13 contain this in the known issue section:
- Using Swift packages with binary targets may result in a “no such module” error when attempting to import the module of a binary target. (77465707)