I have personally seen both approaches implemented.
Company 1 took the approach of updating a procedure, releasing it, and having employees train to it. The caveat here is that their change control procedure said that process changes are expected to be implemented by the various sites within 30 days of a procedure update. So technically the procedure could be updated and sites would have 30 days to come into compliance. Employees had 60 days to complete the training, before they were considered "past due." This was a ~15k employee electronics manufacturer with more than a dozen manufacturing facilities around the globe.
Company 2 took the approach of a procedure change being "approved," then training conducted, then the procedure change being made effective. The company would require employees to train to approved updated procedures, but then would send a follow-up notification when all training had been completed and the change was made effective. This was a smaller, although still several thousand employee medical device manufacturer, with multiple global sites.
Neither of these companies had received significant external pushback (that I am aware of) about their chosen approach. Both were 13485:2016 certified.
As others have said, I think its ultimately about having a defined, consistent process that works for your organization, and making sure people follow it.