I was told that according to one of the King Acts, that one can only store documents outside our borders if one has dispensation from SARS.
If this is correct, can company data be stored in a cloud which isn't hosted in RSA?
Not with POPI. This will become quite tricky as POPI defines multiple entities: "Responsible Party" as the owner (don't confuse with the "data-subject") of the data and "Operator" as the cloud owner for example (or hosting provider etc). Even in local context (i.e. you host with an ISP) this becomes tricky as the "data subject" (you, the owner of the data) has to give consent of the data to be transferred across borders (the consent needs to be given at the point where the data is gathered).
Typically I (the responsible party) would sign a back-to-back agreement with the operator to ensure that the data is stored and protected according to POPI standards (last time I checked, the act did not make any specific mention of minimum encryption, storage etc). Most overseas providers already have "blanket-agreements" in place such as safe-harbor policies (this is also tricky, because the "old" EU-US safe-harbor policy was replaced with "Privacy Shield") but jurisdiction will always be a sticky point. I think this becomes even more of an issue, where a cloud-provider has POPs across multiple territories with different legal frameworks (it is "relatively easy" to exercise law agains US/EU entities, but what about a breach in a middle-eastern POP?).
None of the above really is a concern for the data-subject (you), as you will exercise South African jurisdiction and the Responsible Party (the entity using your data) will be accountable for any POP violations / compliance issues. This might often be challenging as the Responsible Party might not necessarily know that data-subject information is being transferred to a foreign country (i.e. there are plenty of bulk SMS/email services in SA, most of which use AWS or POPs in India for bulk-transmission)
When I was still in banking SOX / Kings started to surface and back then it was focused mostly on record keeping - i.e. you could very well have physical company documentation stored in a compliant vault overseas - I would guess that Kings/SOX would have grown to cover electronic storage since then (it's been a good 15 years since SOX and King II - so much would have changed).