it shouldnt have to plot the whole route - all it needs to do is check the direction and move focus 1000k towards say the bookmarked system. then it picks a star there just under 1000 ly distant and plots the route back to where you are. thats how i see it working. it only needs the direction of the bookmark, not the whole route there.
as to the storage thing, i like to have local storage but most people are dumb and trust everything 'to the cloud' and this brings two issues: 1) unless you pay for much storage, it fills up pretty fast with junk and 2) once hackers figure out how to take the cloud down or offline, you pretty much have a useless piece of hardware at home, with only a small ssd for the os, a slightly larger hdd for the game installs, and no local save files so you cant play without starting over (Assuming the game even lets you store saves locally)
i suspect the reason any storage issue might come into play is because of computers designed deliberately to use the cloud and with not much local storage.