I got the following message:

Fatal Error: Unable to contact the WSUS Service. Please verify that Windows Server Update Services is installed and running on the local machine.

However, when I checked WSUS logged messages everything looked good.

Get-WinEvent -FilterHashtable @{Logname='Application'; Providername='Windows Server Update Services'}

In fact, I was running my command from a PSSession, and that’s why I had this error.
As soon as I ran it from inside an RDP session, the WsusUtil command worked fine.

Done. Please check event log for events with source "Windows Server Update Services."

Of course, if you get the same error message from inside an RDP, you have to investigate further about the WSUS service.