As Princy has pointed, there is no build-in paging functionality of the RadTreeView.
Regarding your options of implementing such a functionality, my suggestion is to use the second one. There is though some limitation. In order to achieve this functionality you should not use the build in web service functionality, but call the web service method manually and then creating the items on the client-side filling them with the data returned from the service method.
the Telerik team