From what I'm reading here http://developers.marketo.com/documentation/rest/get-lead-activities/ :
"For the first call, use the Get Paging Token API to get nextPageToken. For subsequent calls to this endpoint, use the nextPageToken returned from the response. This endpoint will always return the nextPageToken."
The nextPageToken is provided by the Get Paging API but only for the first call. You are correct in that after making the first call the nextPageToken from the GetLeadActivity is used.
In the table below that for parameters it states the nextPageToken is required. If I do a call without the token I get the following response:
"message": "Missing value for required parameter 'nextPageToken'"
So to make the first call I do need to call Get Paging API and without knowing what date to use, makes grabbing all the activity for a lead impossible.
You say there was some dev in that past to get the data. It seems that is in the SOAP API but not the REST API.
I would put the date at which you started to use Marketo, or, if I do not know the date the instance started, 01/01/2006, as I think Marketo was not even created at this date. You'll be sure to retrieve all the lead activities.