Hi,
That means, that the navigation search is very likely hard-coded into the theme files, and it is not automatically replaceable. If there is a page builder/theme builder included with the theme, then there might be an option to replace the search with a shortcode.
If not, then you might have to ask the theme author if there is any way to replace the search bar via a custom hook, or if not, then which theme file has it hard-coded.
Then, if you need help with the replacement, you can add temporary FTP and back-end details, and I will happily do it for you.