It is possible to change the template of News paginate following the information below.
Once created News folder template and customized list and details find the file Index.html in the folder /news/Templates/ViewHelpers/Widget/Paginate/
Create a copy of this file (MyFile.html) in the same folder and change the layout as you want.
In order to include correctly the new template insert in the page setup the following row including the name of the html file:
plugin.tx_news.settings.list.paginate.templatePath = sitePath/news/Templates/ViewHelpers/Widget/Paginate/MyFile.html