How secure is the telnet protocol?

The telnet protocol is not secure at all. Your entire communication is sent unencrypted over the network. Hence, you should only use the app on a trusted network that cannot be reached from the outside (this is usually the case with any home network).

If you cannot trust your network but want to use Remote Keyboard anyway, then the suggested method of connecting is to tunnel your network connection through an USB cable. To do this, you need to have the android SDK installed, then open a commandline and issue the command

adb forward tcp:2323 tcp:2323

Afterwards connect to localhost on port 2323 instead of the port, the app tells you to.