The phrase would have (in this context) indicates that the following clause describes a counterfactual situation that did not occur, but "would have" occurred in the past if the condition described previously were true. The part of the sentence before would have describes a hypothesis; the part after would have describes a consequence of that hypothesis.
In other words, if the people were anyone other than the early Puritans of Boston, then their grim, rigid demeanor would indicate that something extraordinarily serious and awful was about to happen, like the public execution of a criminal. However (as is explained in the next few sentences), the early Puritans of Boston commonly took on the same grim demeanor when attending to small matters as well as large matters, including whipping a misbehaving child or escorting a drunk Indian out of town.
The idea is that the Puritans were very unusual people: they took everything very, very seriously. The postures of their bodies and the looks on their faces became as grim and stiff when they attended to small, commonplace matters, as the postures and looks of other people become when attending to the most serious and awful matters, such as publicly hanging a murderer.
But why is it “would have + past participle”?
Normally have + past participle means the perfect aspect. Here it means the past tense. The reason for this abuse of the word have is that augured some awful business… is in the conditional mood, but English has no word that clearly specifies a past-tense conditional mood. If you say would + infinitive, that would suggest that the imagined consequence happens in the present or the future. If you say only have + past participle, that would suggest that the consequence really happened (if the hypothesis were true).
So, in English you say would have + infinitive to indicate a consequence that, if it had happened, "would have" happened in the past. Yes, this is strange and confusing, because the same construction also fits a consequence in the future. For a brief explanation of why English grammar has these nonsensical and ambiguous constructions, see here.
The reason for saying would have augured instead of would augur is mainly to reinforce the fact that the story is set in the past. Would augur would still be correct. But would have augured reinforces the fact that the "grim rigidity" did happen (in the story) even though the auguring didn't.
By the way, augur is not a commonly used word today. Today we would might say imply.
The revision
This:
The grim rigidity that petrified the bearded physiognomies of these good people would have augured some awful business in hand if it had appeared/occurred amongst any other population or at a later period in the history of New England.
is perfect. Nathaniel Hawthorne himself could have written it. (Notice that could have works just like would have. It's another past tense for an imaginary situation, abusing have to avoid sounding like the present tense.) I took the liberty of removing a comma after population, so the or phrase is more clearly governed by the if.