Now that you have the system fully updated, try another kernel and see if the shutdown works. I guess there are no issues with reboot … If with another kernel works, then maybe there is a regression on the one you are currently using.
Maybe you share some more information about your system as described here: