Your scripts probably have DOS-style CR-LF line endings and not Unix-style LF line endings. The ^M seen in the error message in the first case is an indication that the 0D character was interpreted as part of the script interpreter name and not as part of the line ending (as one might expect it to be). Since there is no executable file on your system with a path that includes the character 0D (^M), the system is not able to invoke the interpreter. When you manually call your interpreter, it is able to handle both kinds of line endings present in the script.
If you convert the scripts to use Unix-style LF line endings, you should see the shebang working. Read on for an illustration.
In the session below, todos and fromdos are a utility (available on Ubuntu as the package
tofrodos) to convert the line-ending conventions from CR-LF to LF. Any equivalent utility (see this unix.SE question) would do for the purpose of demonstration.
The following session transcript (executed with your same script files) should clarify the situation:
$ fromdos hello.sh
$ todos hello.sh
bash: ./hello.sh: /bin/sh^M: bad interpreter: No such file or directory
$ fromdos hello.py
$ todos hello.py
: No such file or directory
It seems that it is the kernel that reads the shebang line, and apparently the Linux kernel (at least as of the version on my Kubuntu Saucy system) does not recognize the CR as part of the CR-LF line ending convention.
If the shebang of your script doesn't seem to be working (i.e. manually calling the interpreter on the script works but you can't execute the script using its file name even though you have done
chmod +x on it) then this is a possible reason.
Thanks to the others who commented too. I'd also be happy to hear if there are better answers!