Apache has a problem with interpreting the shebang line if the script is encoded in utf-8.

However, when I encode the script in utf8 the error log shows a "premature end of headers" error.

You would not get that error if the script was properly utf-8 encoded. The only time I've seen that error when encoding was improper (like improperly converting a utf-8 encoded script to ascii).