I am using wp-paginate to setup page numbering, but regardless, as soon as I try to go to the next page, eg: http://domain/page/2 I get a 404 error (only on index page). why?
This has nothing to do with my theme but your hosting setup. Probably you don’t have proper rewrite rules defined in .htaccess or .htaccess are not working in general. There could be other things as well but this is not theme related.
Does your regular Posts/Pages are working correctly?