Since the Genesis device is deployed via a physical projectile, I think the Borg would detect it in advance and stop it from ever reaching them
...If the Borg realized that a Genesis device was approaching, that is. The Borg do not stop all threats as a matter of course - they let through things they do not perceive as particularly threatening, such as shuttlecraft in the middle of a battle in "BoBW".
Of course, the device could be detonated at a distance. The effects of the device detonated by Khan propagated through empty space nicely enough. Whether they could have been stopped by starship shields is unknown, as Kirk's ship suffered from a twofold lack of shields (nebula disrupted them, main power was down) when David made his expert evaluation that they were all going to die. Whether Borg shields would fare better than Starfleet starship shields is another unknown variable.
Well, since the Star Trek universe isn't engaged in a Cold War with Genesis warheads, I think we can assume they found some way of neutralizing it offscreen.
I wouldn't bet on that. The Trek superpowers and even second-rate empires are shown to possess impressive weapons of mass destruction, such as techniques to set an entire atmosphere aflame ("The Chase"), make a star flare ("Shadows and Symbols"), or turn all life to dust (ST:NEM). Yet these weapons only see sporadic use, which is a worst-case scenario for us Trek apologists, as it debunks two possible explanations in one blow: it can't be a case of Mutually Assured Destruction or else the side being hit would retaliate in kind, and it can't be a case of existing defenses or else the side being hit would defend itself.
Which isn't to say nobody hasn't tried it - recall the Dominion tried to use a protomatter device to induce a supernova in the Bajoran sun, but that plan seemed to heavily depend on the fact that nobody was expecting it.
Or then the whole point was to make everybody notice it and worry about it, so that attention would be diverted from the real threat, which was the jamming open of the wormhole. Heck, we don't even know if the Founder had any protomatter bomb for real - it might have been pure bluff. Why else would the Founder deliberately have blown its cover and invited the heroes to a chase? Dropping a bomb into the star could have been done in total secrecy if the Founder so wanted.
Protomatter also returns in "Second Sight", where Gideon Seyetlik uses it to reignite a dead star. Either the substance got safer in the intervening century, or then its supposed unethicality in ST2/3 was not due to safety issues at all. Perhaps Marcus wasn't a good sport for using the easy way out or something?
Timo Saloniemi