How can I use Powershell as my tramp-encoding-shell?

So I dont know TRAMP but the explanation of what you get is that Windows PowerShell send you back unicode (UTF16), each character is 16 bits in this case the letter an a zero, plus the fact that the End Of Line is carriage return / line feed (0xa, Oxd).

Now for "emacs could not find local shell prompt for PowerShell" error according to TRAMP documentation @Michael Albinus advice seems to be promising.

6.4.2 Running shell on a remote host

Calling M-x shell in a buffer related to a remote host runs the local shell as defined in shell-file-name. This might be also a valid file name for a shell to be applied on the remote host, but it will fail at least when your local and remote hosts belong to different system types, like ‘windows-nt’ and ‘gnu/linux’.

You must set the variable explicit-shell-file-name to the shell file name on the remote host, in order to start that shell on the remote host.

6.4.6 Running remote processes on Windows hostsWith the help of the winexe it is possible tu run processes on a remote Windows host. TRAMP has implemented this for process-file and start-file-process.

The variable tramp-smb-winexe-program must contain the file name of your local winexe command. On the remote host, Powershell V2.0 must be installed; it is used to run the remote process.

In order to open a remote shell on the Windows host via M-x shell, you must set the variables explicit-shell-file-name and explicit-*-args. If you want, for example, run cmd, you must set:

(setq explicit-shell-file-name "cmd"      explicit-cmd-args '("/q"))

In case of running powershell as remote shell, the settings are

(setq explicit-shell-file-name "powershell"      explicit-powershell-args '("-file" "-"))