Output entries sorted by category title and paginate
Not exactly what you're looking for, but it gets you closer.  This should display the order you want, but it doesn't have any pagination (and honestly I'm not sure if that's possible using Craft's {% paginate %} tag along with your other requirements.

IMO, you're probably going to be better off doing this in PHP either using a Template Hook or a custom plugin.

Regardless, here's the Twig code:

{% set allProjects = craft.entries({
    section: 'projects',
    order: 'title asc'
}) %}

{% set categories = craft.categories({
    relatedTo: allProjects,
    title: 'not Unknown',
    order: 'title desc'
}) %}

&lt;ul&gt;
    {% for category in categories %}
        &lt;li&gt;{{ category.title }}&lt;/li&gt;

        {% set relatedEntries = craft.entries.relatedTo(category).order('title asc') %}
        &lt;ul&gt;
            {% for entry in relatedEntries %}
                &lt;li&gt;{{ entry.title }}&lt;/li&gt;
            {% endfor %}
        &lt;/ul&gt;

    {% endfor %}
&lt;/ul&gt;