Data replication systems need two use cases:
- Initial loads or syncs, where you obtain all data for some object to persist.
- Incremental or real-time updates during use.
You've identified some of the features that suit those use cases.
sObject Get Updated and Get Deleted are solutions for (2). It is their design purpose to be used for polling in data replication. If you want to use real-time (push) replication instead, look at Change Data Capture.
Query All is a potential solution for (1), but at larger data volume you should definitely be looking at the Bulk API rather than the REST API. The (asynchronous) Bulk API is designed for extracting and loading data efficiently at massive scale.
The If-Modified-Since header isn't really going to help you on large-scale data replication. It would only provide notification that a specific, relatively small set of sObject Ids had not been modified; that is, it's an inefficient form of polling.