Turns out it's not only Windows 8 that has its telnet client disabled, Windows 10 is in the same boat. I've been using Windows 10 for quite a while now and just discovered this issue. Anyway, the way to enable is as follows:
- Right click on the start button
- Select "Programs and Features"
- "Turn Windows features On or Off"
- Select 'Telnet client' in the dialog box that appears, like here: