You can go to this wiki page which has a list of all of the NCN routes; http://wiki.openstreetmap.org/wiki/WikiProject_United_Kingdom_National_Cycle_Network/National_Routes
Note it lists the route relations for each of these. If you click on the little “a”, it takes you to the relation analyzer, which has the option to download a GPX. Specifically for NCN route 4, this is the link: http://betaplace.emaitie.de/webapps.relation-analyzer/analyze.jsp?relationId=2204
So you can download the GPX from there. I don’t know how you would load that into your Garmin, does it work as a mass storage device?