Is the datasource a FileGDB when you ran into this issue i.e. pagination fails unless you add ObjectID field?
if so, it happens due to a known bug with FileGDB.
In general pagination in ArcGIS Server needs Order By field(s), if you don't specify anything in Order By, it uses ObjectId fields as a default field to sort records (pls see the 2nd bullet in "What's new in 10.3" section in ArcGIS REST API help topic).
When you specify OutFields (without ObjectID field in there) but nothing in Order By, the sql that goes to the database looks something like 'SELECT F1, F2, F3 FROM TABLE1 ORDER BY ObjectID .... ".
FileGDB does not like it when fields in Order By is not part of the SELECT list.