It could be advertised via Google's Nearby Bluetooth API

Nasty, ugly, closed.

Prefer: normative, specified, open. Gimme Physical Web, please. Which has a mdns protocol- it's kind of funky tbh, but at least your not enjoindering yourself and your users into a silo.

The lucrative thing about Google Nearby is that it works across iOS and Android and since it has an option to fallback using sound (ultrasound?) it can work on any device which has a speaker and mic[1]. Are there any open solutions which lets me simply pass messages between 2 devices without any sort of configuration? BT LE is ruled out (for now) because I can't rule out pre-Lollipop devices[2]. I wish there was a more universal and open protocol which was fast, reliable and worked on most mobile devices to simply exchange small packets of data.

[1]: Of course it doesn't have support for Windows 10 Mobile, but not due to practical limitations.

[2]: BT LE in 4.3,4.4 has lot of issues and limitations

Edit: added caveat about not supporting Windows 10 Mobile

Then WiFi Direct for something already supported in Android.

Hasn't Google been pushing for Physical Web, and baking support for it into Android? It was a big thing at last year's Chrome Dev Summit.