There is no newline trim at the begin of wikitext, which can also results in this output for html comments, see T25698, which is talking about T6161

Looks related, but maybe not.

Related, but not the same. Category/language links are not handled equivalently to comments w.r.t. whitespace squashing. Consider the first snippet above,

First paragraph

[[category:foo]]

Second paragraph

is parsed as

<p>First paragraph </p>
<p>Second paragraph </p>

but

First paragraph

<!-- comment -->

Second paragraph

is parsed as

<p>First paragraph </p>
<p>
<br>
Second paragraph
</p>

Comments (1) and (2) suggest that this is how HTML comments work, but there is still some squashing e.g. around multiple comments on successive lines -- this snippet is parsed exactly the same way as above:

First paragraph

<!-- comment 1 -->
<!-- comment 2 -->
<!-- comment 3 -->

Second paragraph

The rules for whitespace squashing around category/language links are even more elaborate, except at the top of the page where all cause the same issue.

What's interesting is that if the first paragraph after the category/language links at the top starts with a wikilink, then it is parsed correctly:

[[category:foo]]

[[First]] paragraph

is rendered as

<p><a href="/index.php/First" title="First">First</a> paragraph</p>

i.e. without the <br> tag.