How to display paginated posts from all categories?

A basic WP_Query instance and loop will work (untested):

$posts = new WP_Query( array(
    'paged' => get_query_var( 'paged', 1 ),
) );

while ( $posts->have_posts() ) {
    $posts->the_post();

    ...
}

$current_page = 1;

if ( isset( $_GET['paged'] ) ) {
    $current_page = absint( $_GET['paged'] );
}

echo paginate_links( array(
    'base'    => add_query_arg( 'paged', '%#%' ),
    'total'   => $posts->max_num_pages,
    'current' => $current_page,
) );