Try using Bundler to manage gem dependencies instead of vanilla
jekyll serve. You probably have multiple versions of the gems installed and that could be causing you issues.
Gemfile with the following
source "https://rubygems.org" gem "jekyll" gem "jekyll-paginate"
bundle exec jekyll serve or
bundle exec jekyll build
You could also try
gem uninstall jekyll-paginate and remove all but the latest version.