改行にマッチしたいときは不用意に$を使うとどつぼに嵌るということですな
$text =~ s/^\s*\n/<p>\n/mg;
とするのが正解？