In most macOS applications ControlEnter works, and in Excel ControlAltEnter works in cells, and even in Find and Replace it will enter a space, but it doesn't appear to search.
\n which is an escaped new line doesn't work, nor does copying and pasting a new line character from another application.
^p works as an escape character but again not in Excel.
It looks very much like this isn't possible in Excel for Mac. The best thing I could suggest at this point is to ask for Microsoft to fix this via their feedback forum:
The last option I was going to suggest was using Numbers which is the Apple version of Excel, it works very well in general but has the same limitation from my testing.
Last option would be to use Excel for Windows via a Remote Desktop application like Citrix, a simulator like WINE or a virtual machine like VirtualBox, Parallels or VMWare.