Pausing the song would be too abusable, IMO. I suppose if only the host was allowed to do it that'd be ok...
A message like "Beatmap downloaded" might also get in the way... I think it's distracting when it does that at the minute, but it's not that bad I guess. >_> In this case it would be triggered when even a single player asks to retry, though, which is probably going to be most of the time in 8-player games (right at the start if there's a newbie playing), and maybe multiple times throughout the song depending on how it's coded. .-.
I think it should be as unobtrusive as possible. A chat-line style notification would probably do...?
Or,
In my case, I'm always looking at the scoreboard during a map anyway, so I think that'd be a good place to put stuff. Perhaps, rather than a "Yes/No" for retry, you could just have a single retry button/option, which would mark your entry on the scoreboard as "Retry?" or something (and maybe change the colour to make it stand out), and if over half of the players mark themselves like that (either by letting others retry or feeling themselves that they want to retry), the game restarts? (Or, that gives the host the power to restart?)
It'd be nice if there was a small break (5 seconds or so? Or, proportional to the time into current map?) before restart actually happened as well, as repeated sudden restarts have the potential to dramatically extend the time spent playing without a break (i.e. hullo hand cramps).