It would be interesting to know which standard you were being audited against for this as that might impact the response.
Physical labelling risk
Firstly, is physical labelling a good second step? Yes but it depends on your processes on whether this is necessary. In some warehouses, pallets are not practically accessible and a hold may occur over many pallets so if you put in a requirement to label every one physically, that might be impractical and slow.
Also, depending on how your WMS works, bringing your pallets out to label them may introduce risk. Some block processes in a WMS actually stop pallets from being moved at all. So to get them to an accessible location, you have to unblock them.
Lastly, after all of that, if the pallet is later accepted and taken off hold, you need to be sure you remove all labelling from the pallet or risk rejection at customer.
So that's all the problems with labelling.
BUT there are also potential problems with your system as is and it depends a lot on how it's designed and how you operate your warehouse.
Possible problems with your process "as is"
Does the automated hold system still work if you have any picking processes? Or is it a risk that once a pallet has gone to picking that it will just be used unless physically labelled?
Is there any occasion where a pallet could be removed from the warehouse without being scanned? While you have processes in place, how do you know they're always followed etc.
Lastly and this is the only one which really started to ring alarm bells for me from your description. Are you using appropriate hold states not using a "pending release" state for products which might have a food safety or quality issue? The reason why is that pending release state (or what you describe as "initially set to hold after production") is not, in many WMS actually a "true" hold. What do I mean? What I mean is that the pallet can often still be moved when on this status but not issued. While on paper if everything is always done to plan, that works, it's also in a status where the majority of pallets are normally released and there is no differentiation between "hold for good reason" and "pending release" status. The reason I worry is because you've said in your description that the pallets then progress to one of two states; release or reject. This must therefore mean that when you do have a QFS issue, you are leaving some pallets in the same status as those pending release. I can tell you from bitter experience, that's where mistakes can happen. If possible, for example, if you have a SAP system and your pallets are produced in QI (quality inspection) status but an issue is detected before they're released, that they are transferred to B6 or some other blocked stock status before the decision is made, while you're investigating. That way your planners aren't seeing it as good stock, your operators aren't assuming it will be released, the pallets can't physically move past automated systems and your quality team are less likely to make a mistake.
Of course none of that is actually about physical labelling but what I'd do once you've assessed all your processes and the risks of labelling or not is record it all in a risk assessment as to why you've made the decisions you have. For example, you may choose only to physically label pallets which have gone to picking if you have that process because labelling other pallets has risk as detailed above.