BLE beacons use advertisement packets with a payload, and at the end of the day, are sent actively by an application (like COVID tracing). With MAC address randomization, it's possible to make them anonymous and untrackable at the protocol level. This paper uses data from the physical layer to pull more metadata to track devices, ie. error and drift in its RF frontend. It's not, not a concern, but it's also not data you'd be able to grab with a normal BLE chipset in sniffer mode. You'd likely need an SDR, and that's what they use in the paper. It's an attack that's on a different level of sophistication and cost.
Additionally, I wouldn't worry too much about beacons on their own (at least, in this context). Beacons are just a form of BLE advertisement packet. Your BLE devices need to send out advertisements anyways to let your phone to know they exist and connect to them. I assume this attack works on any advertisement packet (and also data packets to a connected device). Normally, rotating private addresses will mitigate some attacks tracking two devices talking to each other, at the protocol layer. This paper is more just a broader look at what features you can extract at the physical layer with an SDR to identify a specific device or chipset.
I suspect if many people knew how much their phone was broadcasting to the world around them they'd be quite unhappy. I know I'm rather disgruntled at how much my phone talks and how little I can control it outside of manually toggling it on and off with use.
So, just to get the obvious out of the way, all competent dev teams enable random addresses. It's a no-brainer and it has no effect on the usability of most BT products.
Regardless, even if they do that, the payload of the advertising packet is still useful for tracking purposes. You're probably relying on hueristics at that point, but you can also rely on some devices including a service UUID, device name, or some very specific information in the manufacturer-specific data field.
Yeah, at the end of the day, you're probably going to advertise with some sort of unique short name (so humans know what to pick in the a connect/pairing menu), and have at least one Service UUID (even if you only expose the juicy stuff after bonding.) But that still pushes it back up to a software policy concern, and it's up to the developers to make the appropriate privacy/security tradeoffs. The only real way around this is to do discovery out-of-band via NFC or QR codes or something.
The other detail worth mentioning is that generic service advertisements and beacons will have different behaviors and payloads, since they have different goals.
With the former, the device is advertising because it's disconnected and needs to be discovered. Service discovery necessarily means you're sending out some sort of information about what you are. If it only expects to be connected to one device (ie. the phone), it's going to turn off advertising when connected to said phone. You technically don't need to advertise the service UUID either once you're bonded, although I don't think would happen much in practice, as it makes recovering from an unbond event harder.
Meanwhile, a beacon is data that is intentionally being broadcast out to the world by an application. The application will probably send out beacons regularly no matter what, since that's usually the point (Find My, COVID tracing, etc.) I would expect companies like Apple to ensure that these advertising packets aren't leaking any identifying information. This is easier to do than the above case, because the goal isn't service discovery, but to intentionally broadcast a piece of (anonymous) info.
tl;dr Beacons are fine, especially in comparison to your headphones or smartwatch loudly announcing itself to the world because it's disconnected
Additionally, I wouldn't worry too much about beacons on their own (at least, in this context). Beacons are just a form of BLE advertisement packet. Your BLE devices need to send out advertisements anyways to let your phone to know they exist and connect to them. I assume this attack works on any advertisement packet (and also data packets to a connected device). Normally, rotating private addresses will mitigate some attacks tracking two devices talking to each other, at the protocol layer. This paper is more just a broader look at what features you can extract at the physical layer with an SDR to identify a specific device or chipset.