Most likely, the problem is that there are two separate webparts in Search Center: Core Results Web Part and Search Paging Web Part. And while Core Results Web Part supports asynchronous functioning, the paging webpart doesn't seem to have any ajax-related properties.
Actually, CoreResultsWebPart is inherited from DataFormWebPart - that's why we've got the Ajax parameters section, and the DataFormWebPart undoubtedly does support asynchronous postbacks.
So I assume if you want to configure AJAX paging, the only option could be to give up the Search Paging Web Part, and try to implement paging through XSLT. Probably it will be not very cool paging, but it will be asynchronous.
To implement paging using XSLT, you have to add some XSLT code to CoreResultsWebPart, as described in the following article:
I haven't tried this solution myself, but the idea seems logically strong :)