This sounds like something that a simple, well-formed query_posts() call can do. I doubt that you'll even need to rely on a plugin. :)
I'm going to assume that you're familiar with the query_posts() function, so let's go ahead and use this example as a base:
// let's get the first 10 posts from category ID 3
query_posts('posts_per_page=10&cat=3');
while(have_posts()):the_post();
// do Wordpress magic right here
endwhile;
Now, to get the 11th to 20th posts from category 3 (that is, the NEXT 10 posts), we'll want to use the [offset] parameter of query_posts():
// let's get the next 10 posts from category ID 3
query_posts('posts_per_page=10&cat=3&offset=10');
while(have_posts()):the_post();
// do Wordpress magic right here
endwhile;
For most purposes, that should be sufficient. However, you did mention that you plan on paginating category post lists from the main page alone? I'm assuming that you mean that you have multiple category post lists on your main page, and all these are paginated independently.
With something like that, it looks like you'll have to work a bit with Javascript to do the work for you, along with what I illustrated above.