The storage issue for such a short period of time shouldn't be much of an issue, with a little bit of looking around you should be able to find a decent hotel/guesthouse that caters to travellers and they are usually only too happy to store bikes for a small fee, sometimes free.
Very easy to do in Dar Es Salam where almost everyone leaves their bikes at one of the overlander camping spots while they head over to Zanzibar.
But for flights, the most options and hence usually the best prices are to fly in and out of the main hub cities. Nairobi is one and of course South Africa, either Jo'berg or Cape Town. I'd do a quick travelocity search of flights to your destination city to get a sense of which one has the best prices and go from there. JJ's is Jungle Junction, most overlanders stop there and he stores a lot of trucks and bikes for people. Have a good ride