Can I change the keyboard shortcut for search?

Not within Agenda itself, but the system preferences have a way to do this, if you go to Keyboard > Shortcuts > App Shortcuts, you can create a new shortcut for a given menu command:

Note that the … are not three period but ellipses (alt/option + ;)