A friend brought yesterday his ps4 controller and I was able to pair it with recalbox 4.1 by doing the following.
I pressed the PS button to start it and while blinking I pressed the little button behind the ps4 controller to reset its paired devices.
I turned on the pairing mode of the controller by pressing PS+SHARE buttons simultaneously, until a very fast blinking is noticed.
On recalbox I looked up for controllers to pair and "Wireless Controller" came up, chose pair and the controller worked out of the box without further configuration. The PS button is the hotkey by default by the way.
I'm following this exact setup and I still get cannot find controller, while the thing is right next to the box blinking ready to pair.
Weird thing is, if I plug it in via usb, it works fine. And no, I tried pairing it while it was connected via cable and without, neither way worked. Anything else I can try? Seems some peoples "just works" and others ..well... doesn't.