This might do it, untested, no experience with it, just going by the error–

use Encode;
$doc->extendText($p, encode_utf8 $header);
[download]

The error seems to indicate the $doc expects raw bytes instead of characters.

Update. Tested now, I was right. Need both the above and the second one I missed–

$p = $doc->appendParagraph(text => encode_utf8($header),
                           style => "optionalParagraphStyle" );
[download]

Creates a doc with these two lines–

בס״ד
בס״ד