I don’t think a single colon should have its own, it semantically makes no sense. I see two solutions:

• Wrap the link and the colon+space together in a separate element:

<div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><div class="catlinks-title"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: </div><ul><li><a href="/wiki/Category:Example1" title="Category:Example1">Example1</a></li><li><a href="/wiki/Category:Example2" title="Category:Example2">Example2</a></li>

• Make it very semantic, using an <h2> and adding the colon in CSS:

<style>h2.catlinks-title { all: reset; } h2.catlinks-title::after { content: ": "; }</style>
<div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><h2 class="catlinks-title"><a href="/wiki/Help:Category" title="Help:Category">Categories</a></h2><ul><li><a href="/wiki/Category:Example1" title="Category:Example1">Example1</a></li><li><a href="/wiki/Category:Example2" title="Category:Example2">Example2</a></li>

(with i18n and putting the styles in an external stylesheet, of course). In this case, maybe we would need to wrap the whole box in a <section> or something like that, potentially breaking many gadgets and user scripts.

Tacsipacsi solution seems reasonable, will it be added?

There is no “the solution”, I listed two solutions above, and there may be even more. This is a design decision I, as an outsider in this area, don’t want to take on my own. I hoped that that the someone experienced/responsible in this area would step in, but maybe it turns out to have been incorrectly tagged, as the display of categories belongs rather to the interface, which is why people interested in categories didn’t respond. Let’s give MediaWiki-User-Interface a try.