Although getting an error 404 with pagination in wordpress is quite common to come across, the usual suspects are not the way to go if you have a setup with symfony and wordpress working together on delivering a website.
In my setup, symfony accepts all requests while loading wordpress at the same time. This only applies for those requests with do not match an actual file in the file system of the server, such that assets can be delivered by the webserver directly. If there is any entry in the symfony routing that matches the request, then symfony answers. If not, it passes the request on to wordpress which does the same again. This way, I only have to set up a error handling page in wordpress but not in symfony.
When you use pagination, the request will look like /page/2. Now for symfony, there is typically a default route matching /a/b which refers to action b of module a. If you do not take any measures, this default route stops the request from being propagated to wordpress. Hence, you have to add the following lines to your apps/APPNAME/config/routing.yml in symfony:
pagiation:
url: /page/*
param: { module:wp, action: index}
This should be right in front of your default route, which should look like this:
default: url: /:module/:action/*
This applies to custom defined category labels and keyword labels in wordpress, as well.