No, this isn't the NAS I was poking at a few years back - that I solved by getting a slightly newer NAS with a more complete Linux install including compiler. Today's target embedded system is a 3DS, using the devkitARM toolchain.
Anyway the answer was surprisingly easy but not at all intuitive: in the project properties go to C++ Build and on the Builder Settings tab tick Generate Makefiles automatically but don't apply the change yet. Then go to C++ Build → Settings and a new Tool Settings tab will be visible. Select Cross Settings and fill in the correct path and prefix (including the trailing hyphen, so something like "arm-none-eabi-"). Finally go back to Builder Settings and untick Generate Makefiles automatically, and now you can apply the changes. Right-click on the project, pick Index → Rebuild and all the broken includes should sort themselves out.
That solved most of my problems but still left Eclipse whining about some unresolved includes. That turned out to be because the code I was looking at wanted a newer C++ standard - to fix that go through the rigmarole to make Tool Settings reappear and under Cross G++ Compiler → Dialect pick the appropriate standard. Or if the one you want isn't listed, then enter the option in Other dialect flags (for devkitARM I needed "-std=c++14").
I still had to manually add the header path for libctru and a couple of defines that were in the Makefile, but that's fair enough - it's getting the system headers all sorted that's the hard part!