WINRM is a Windows (not PowerShell) service. PowerShell makes use of it, though.
Have you configured WINRM to allow the use of NTLM authentication?
You can check it like this:
winrm get winrm/config/service/auth
The result should look like this (NTLM isn't allowed on this machine):
Auth
Basic = false
Kerberos = true
Negotiate = true
Certificate = false
CredSSP = false
CbtHardeningLevel = Relaxed
You can set it like this:
winrm set winrm/config/service/auth @{NTLM="true"}
Also, NTLM has multiple versions. What version are you trying to use? I'm pretty sure that the original LM version is disabled and only NTLMV2 is allow. You can change that using a local security polity or by editing the registry directly.