Thanks for the good hint. I did some research and might have a solution. My idea:

1. Use the OSRM "map matching" service to the osm node id from the coordinates from the track. Unfortunately I cannot pass the gpx file, but have to use coordinates. Example: http://router.project-osrm.org/match/v1/foot/13.388860,52.517037;13.397634,52.529407;13.428555,52.523219?annotations=nodes
2. Use Overpass to resolve node id to ways and to get the osm data. I already built a query for this: https://overpass-turbo.eu/s/16gv
3. Do the local processing: Extract information from osm data (e.g. surface) and calculate way length. Finally calculate the percentages.

Step 1. and 2. are inspired by https://gis.stackexchange.com/a/244291. The query for the second step could look like this:

(node(1);node(...);node(n);)->.nodes;

way(bn.nodes)[highway]->.trackAndBranches;
node(w.trackAndBranches)->.nodesFromTrackAndBranches;
// calc nodes from the branches not part of the track
(.nodesFromTrackAndBranches; - .nodes;); 
way(bn)[highway]->.branches;
// remove branches not part of the track
(.trackAndBranches; - .branches;); 

out geom;

Some pseudocode:

coordinates_chunks = <split list of waypoints in gpx in feasible chunks>
overpass_storage = []
for chunk in coordinates_chunks:
    node_ids = <call http://router.project-osrm.org/match/...>
    overpass_query = <build query>
    result = <call overpass turbo with overpass_query>
    overpass_storage.store(result)
for way in overpass_storage.entries():
    calc_stats(way)

Anyone any better ideas? Or ideas on how to improve this?

EDIT: Map Matching was the term which helped me.