You'll be fine with maps. Is your route not sufficiently flexible to handle you being a little off what you expected? We would roughly plan our route each morning over breakfast - nothing serious, just a 'here, here and here, expecting to be here by evening' type affair By lunchtime it had usually changed (at least in places where there are plenty of roads to choose from). Couldn't tell you where we were staying until we'd arrived.
The downside with paper maps is whether you can read them... The upside is you don't have to worry about charging the batteries, only keeping the map dry. Put them in a map case on a barbag if you have one, or handlebars if not.
Don't over plan, it will spoil a lot of the fun you could potentially have. Just let it happen, and take an "old fashioned" compass - they do come in handy when "temporarily wandering aimlessly" (aka lost) for making the correct decision on direction at junctions if there is no-one around to ask.
As an example last year, we cycled (14,000km/8,700miles) from the UK to the far North of Norway, across to the Russian border with the Barent's sea, through Finland all the way down to Athens, Rhodes and on into Turkey using paper maps alone. Athens was the only time we used the GPS for navigation, to stick to a planned route into (and out of) Athens to find the hotel/harbour uploaded to the GPS using Velomaps (free software) and track points... Otherwise we never used GPS other than for confirming where we were at night (each and every night we took a GPS reading on a basic Garmin GPS 60 and that was for record keeping and sussing out where exactly we had wild camped that particular night...)