Having shortened the chain because of stretch is an eyebrow-raising concept because by the time a full link's worth of slack has developed, that would be an off-the-charts amount of wear. But drivetrain wear probably isn't your problem either way. Also there are other reasons to find the need to remove links, like tuning the position of the axle in the dropouts. It's conceivable to need to remove a link to tension the chain if it started out almost all the way back in the dropouts, but that would still indicate a ton of wear in almost any case.
That the error isn't constant in and of itself isn't necessarily an issue because the cable pull of Nexus 8 shifters isn't constant between clicks either.
If in those 3 years this bike has seen some solid use, it's possible it could be due for a basic internal service with a Nexus/Alfine oil "dunk." There are many questions here about this and whether to DIY it or bring it in. Friction and under-lubrication of the internal parts can cause some issues like you describe. Even if it doesn't solve the problem, it's still maintenance the hub needs. If the mileage is fairly low, like under 1000mi/1600km, this is likely not the problem.
Cable housing friction can also cause what you describe. A quick test is whether the adjustment indicator shows the same alignment after shifting into a given gear from either direction. If it doesn't, friction in the housing is likely causing binding in the cable release direction. This is also a problem that wouldn't be surprising on a bike that's seem some use. Lubrication may help, or you may need a new cable and housing. Another basic test for this is undoing the cable release at the cassette joint so you can manually slide the cable through the housing with your hands. It should be pretty smooth.
If it's not either of those two things, damage to the hub internals becomes the next likely possibility.
