Another trick you can use is to compose this map in a shader from lower-resolution inputs.
You could use a signed distance function field texture for the territory lines to get crisp vector-like edges even zoomed in tightly without spending a lot of texture memory or juggling different sets of tile textures at different zooms (we used this for the topographic contours on our planet maps on Starlink: Battle for Atlas).
This also makes it easy to control the line thickness, if you want to keep borders from vanishing into hairlines when zoomed out or looking to chunky zoomed in: you can dynamically re-draw them with your desired thickness for the current view.
Then the paper surface can be filled in by tiling "detail maps" that you layer based on the zoom level, fading in more detailed/higher frequency tiling when you zoom in, and mipping away as you zoom out.