Hi Abizer,
yes, something like that should be possible. One great feature of plus codes is that nearby codes mostly have the same prefix. This means that, if the user wants to navigate to some location that is new to them, it would be easy to look up all codes already stored on the user's device that start with the same, say, eight characters. This would allow you to help your users find their destination by a statement like "Thomas's home is near Tees Pizza" (assuming that the user already navigated to the Pizza place before).
If there's no known place near the destination itself, something similar could be attempted for nearby tiles (eight characters adjacent to the destination), tiles along the direct route to the destination, or if all else fails for the whole rectangular area that has start and destination in opposite corners. In that case, a navigation statement could be something along the lines of "You want to go to Thomas's home. Looks like Tees Pizza is about half way between your current location and that place."
The above seems to be realistic for users that use the app a lot in the same place (for example their home town), if you cache a good number of previously used locations. It is less realistic to do for the whole country in advance.
I did a quick back-of-the-envelope calculation to estimate what we're talking about. With an area of ~950,000km², I would except there to be on the order of 35,000 six-digit prefixes in use across Tanzania - but each "tile" that could be addressed by a six-digit prefix has a size of approximately 30km². I think it would be possible to find a "best city name" for that number of tiles, for example by outsourcing that task to your users - but that would mostly help with cross-country navigation and postal services, but not really be useful for a step-by-step navigation within one city. This data (35,000 x some bytes for a city name) would probably fit on most user's devices, though, so it could be great to have for offline functionality.
Going from six- to eight-digit prefixes means a factor of 400, so roughly 14M entries - which is likely too massive to either store or build in the first place.