Ok, I found the solution.
I was able to find the IP address of the NAS by running the setup software on one of the newer machines (which started up Firefox to address the NAS, independent of the default browser setting). [In this case, firefox ran on a Parallels VM rather than on my main machine] I could have also found the IP address by examining DHCP settings from a number of sources.
Once I found the IP address, I was able to connect to the NAS using a browser on the older machines (or the newer ones) and turn on AFP. Once that was done, the older machines were able to connect to the NAS.
As far as I can tell, the only thing the NASNavigator software does is launch a web page connected to the NAS admin server.