We don't know how quickly the protections have fallen
All we know is that Shacklebolt has sent his Patronus. We don't know the timeline of events at the Ministry - or even if he sent the Patronus directly or a bit later, after making sure he himself was save. We also know that it takes some time for the patronus to travel to its destination, so we have to keep that in mind.
The Death Eaters were prepared
From the answer you linked we know that the Death Eaters were waiting for the ministry to fall, to use its power to undo enchantments:
“Where are they going to hide the boy next?”
“At the home of one of the Order,” said Snape. “The place, according to the source, has been given every protection that the Order and Ministry together could provide. I think that there is little chance of taking him once he is there, my Lord, unless, of course, the Ministry has fallen before next Saturday, which might give us the opportunity to discover and undo enough of the enchantments to break through the rest.”
We don't know the specifics of the protections, so we can't say for sure how long it takes to break through them, but to my knowledge, there is nothing in the canon that would contradict the possibility of an instantaneous, remote disabling of at least some of the protections.
We also know that the Death Eaters have infiltrated the ministry, so it might have been just a matter of mere minutes after the fall of the ministry for the Death Eaters to do their deed:
"I assure you, Yaxley, the Auror Office will play no further part in the protection of Harry Potter. The Order believes that we have infiltrated the Ministry."
"The Order's got one thing right then, eh?" said a squat man sitting a short distance from Yaxley.
(Harry Potter and the Deathly Hallows, Chapter 1: The Dark Lord Ascending)
There are many ways how people could have detected that the protections have been broken
There are at least two possible explanations how people could have noticed that the protections have been broken.
One, there is a spell which is able to tell whether or not someone is "in grave peril" - we see it in use on the Weasly clock. Granted, the clock itself is not reliable and always points to "in grave peril" - but it's not unlikely that this is due to the fact that it has been enchanted in peaceful times and is therefore oversensitive - it would then be just a matter of fine-tuning the underlying charm to make it work reliably in times of the Dark Lord.
If that's too far-fetched for you, then there is another explanation: A protection against Apparation on the Weasly grounds was part of the protection. In fact, all of the guests enter the Weasly premises on foot:
Brightly coloured figures were appearing, one by one, out of nowhere at the distant boundary of the yard. Within minutes a procession had formed, which began to snake its way up through the garden towards the marquee.
(Harry Potter and the Deathly Hallows, Chapter Eight: The Wedding)
So all it takes is one person disapparating with the signature crack to tell everyone that the protections have fallen. Either someone has tried it out of desparation, or, at least equally likely, someone has forgotten about the restrictions - because after the Patronus left, a panic broke out:
Many people were only just realising that something strange had happened; heads were still turning towards the silver cat as it vanished. Silence spread outwards in cold ripples from the place where the Patronus had landed. Then somebody screamed.
(Harry Potter and the Deathly Hallows, Chapter Nine: A Place to Hide)
