Correct , there was a land station or terminal telegraph point in Madeira where SA-UK bound ships called as a matter of procedure, so as to speed the news on. from Natal by telegraph, via undersea cable, to England.
However, in answer to the question about door to door letter transit time, it is safe to assume 4-5 weeks. In this the time elements were of the order of 24-28 days at sea , the balance being land terminal transit times at either node.
In the annals it is recorded that passing ships wanting to pass urgent news on to each other would sail past each other close enough to read messages written on large blackboards fitted to their superstructures and visible to each other. This method was faster than the use of signaling flags.