As regards Linux, the behaviour can be controlled by with:
(setenv "LANG" ENCODING)
before calling M-x shell and after from the shell buffer with:
(set-buffer-process-coding-system INPUT-ENCODING OUTPUT-ENCODING)
Both should be set to a value compatible with the string to be represented. UTF-8 encoding family should work in most of the cases.
Try M-x cider-connect if you've already started a REPL via leiningen yourself.
cider-jack-in tries to start a repl-server and connect to it. For some reason, this fails, maybe because of the already running REPL, so you might try cider-jack-in without starting a REPL manually first.