Display all posts from all categories with pagination

To be able to order by category, you have to intercept the MySQL Query.

Start with pre_get_posts:

add_action('pre_get_posts','setup_my_query_interception');

function setup_my_query_interception($query){
    if(!is_admin() && $query->is_home() && $query->is_main_query()){
     add_filter( 'posts_clauses', 'order_by_category_intercept_query_clauses', 20, 1 );
  }
}

Now we enhance the MySQL Query to include the term and taxonomy tables:

function order_by_category_intercept_query_clauses($pieces){
        global $wpdb;
        $pieces['join'].=" LEFT JOIN $wpdb->term_relationships trt ON ($wpdb->posts.ID = trt.object_id) LEFT JOIN $wpdb->term_taxonomy ttt ON (trt.term_taxonomy_id = ttt.term_taxonomy_id) INNER JOIN $wpdb->terms termts ON (termts.term_id = ttt.term_id)";
        $pieces['where'].=" AND ttt.taxonomy = 'category'";
        $pieces['orderby']="termts.name ASC, ".$pieces['orderby'];
        //Remove the filter so it only runs once in our main query
        remove_filter('posts_clauses', 'order_by_category_intercept_query_clauses');
        return $pieces;
}

This should result in your main query being put out ordered first by your Category name (pagination should still work).
When doing the loop, you can group your categories like this:

…before the loop:

global $activetax;
$activetax = "";
echo '<div class="mywrapper">

…in the loop:

$cats = get_the_terms(get_the_ID(),'category');
if(is_array($cats)){
    if(!($activetax==$cats[0]->name)){
            $activetax = $cats[0]->name;
            ?>
            </div>
            <h2 id="tax_id_<?php echo $cats[0]->term_id; ?>" class="cat-header"><?php echo $activetax; ?></h2>
            <div class="mywrapper">
            <?php
    }
}
get_template_part('content'); 

… after your loop

echo "</div>";

Didn’t test it, but should work 😉

Happy Coding.