It's not a matter of the state of the installation being wrong. I closed the cmd window that installed deno in and re-opened another window and the environment variables were refreshed properly with the path updated.

Running deno again worked after the cmd window was opened.

Either the process of installation is wrong or windows has a breaking change.