I don't know what's going on with Apple Music. I can rebind Cmd-F to any of its menu items if I do it for all applications, but not if I target Music specifically.
They're likely doing something funky to implement its shortcuts because the standard way wouldn't work everywhere in the app.
Ironically, at this point the cleanest implementation of Apple Music might actually be the Windows version, which as far as I can tell is a fresh codebase written exclusively in WinUI/WinAppSDK. Many hoped that the transition from iTunes → Music.app would turn out to be a blank-slate AppKit rewrite on macOS but that's not what we got.