An incorrect contribution allocation must be corrected, whether the affected participants are HCEs or NHCEs. The plan sponsor would correct this by crediting each affected HCE's account with the shorted match amount plus earnings.
If these incorrect allocations occurred in plan years more than two years in the past, then it becomes important to distinguish if the operational failures were insignificant or significant. If the failures were insignificant, then correction can be through APRSC, otherwise VCR or Walk-in-CAP.
In the situation you describe the factors most likely to determine whether the failures are significant would be the number of years involved, the number of participants affected, the magnitude of the contribution shortages, and the reason for the mistake. I beleive that it is probably significant. Significant operational failures can be corrected through VCR if certain eligibility requirements are met.
Each plan year that is corrected would require retesting for non-discrimination. If any year failed the non-discrimination test after the allocation corrections, then further corrections would be required (QNECs to NHCEs).
Looks like correcting one operational failure might cause a different failure.