Comment Works provides an ElementQuery so you can use the {% paginate %} tags.
The example below creates pages of 3 entries, and shows all entries (pending, trashed, approved, spam) for documentation purposes.
{# @var commentsWork \twentyfourhoursmedia\commentswork\services\CommentsWorkService #}
{% set commentsWork = craft.commentsWork.service %}
{# @var query \twentyfourhoursmedia\commentswork\elements\db\CommentQuery #}
{% set query = commentsWork.createElementQuery %}
{% paginate query.commentStatus(null).element(entry).limit(3) as pageInfo, pageEntries %}
{% if comments | length == 0 %}
<p>(no comments)</p>
{% else %}
<ul>
{% for comment in comments %}
<li>ID:{{ comment.id }} STATUS:{{ comment.status }} FOR ELEMENT:{{ comment.elementId }} TITLE:{{ comment.title }}</li>
{% endfor %}
</ul>
{% endif %}
{% if pageInfo.prevUrl %}<a href="{{ pageInfo.prevUrl }}">Previous Page</a>{% endif %}
{% if pageInfo.nextUrl %}<a href="{{ pageInfo.nextUrl }}">Next Page</a>{% endif %}