How does a bank convert one currency to another? Say for example I sell ZAR and buy USD. What happens behind the scenes so that the local ZAR bank is able to deposit USD into my account? 


Does the bank require some sort of USD cash reserve?
How do the banks interact/negotiate with each other?
What if the bank selling ZAR cannot find a bank/trader selling USD who wants ZAR?
If the bank does find a source of USD, is any physical money like notes/bills/gold ever moved from one bank to another to settle the account? 
How are these transactions regulated or monitored to 
avoid fraud?
Yes, a reserve is needed to ensure the integrity of the money issued (as always).

On the international foreign exchange market, many millions are traded at a time. Otherwise, with smaller amounts of money, the costs of transferring that money (e.g. via SWIFT) would be too high for the amount transferred. That is why investors and small businesses do not trade in the forex market themselves—they go through the financial intermediary.

Banks communicate with each other using computers and telephones. If you collectively put all these many communications together, you get the concept of an international interbank foreign exchange market.
Prices are offered for foreign exchange deals. If the price is fairly high, the bank may not get a sale quickly—they will have to wait, or lower their price. If the price is lower, they will be more likely to find a buyer.
This question is related to the reserve requirement. If banks need to increase their reserve, they will buy securities denominated in that currency (government bonds, stocks, and other financial instruments), as these securities can easily be transferred from other locations. Vice versa: If the financial institution has too many illiquid assets (giving a lower leverage), they could choose to then sell these assets to other financial institutions who need them. So, buying and selling currency is not inextricably tied up with buying and selling reserves, as there is some play between the two. You asked about physical cash—cash is related to the demand for currency (so, yes, some cash is transferred, but not much as not everybody wants to draw cash). And you asked about precious metals—well, those are transferred even less, and only really serve as a 'reserve' to give integrity to fiat money generally.

The rest of my answer is copied from https://kevinkotze.github.io/if-2-forex/ , which comes from Kevin Kotzé's web page https://www.economodel.com/international-finance

1.1 Communications and funds transfers
The enormous volume of trade in the foreign exchange market requires an extensive communication network between traders and a sophisticated settlement system to transfer payments in different currencies between the buyers and sellers of different currencies. Traders are able to obtain information that is provided by major commercial distributors such as Reuters and Bloomberg. The traders are then able to contact each other, to obtain actual prices and negotiate deals. In addition, they could approach a foreign exchange broker to broker a deal, or they can trade on an electronic brokerage system, where quotes on a screen are transactable. When a trade is agreed upon, banks communicate and transfer funds electronically, using systems such as the Society of Worldwide Interbank Financial Telecommunications (SWIFT), which confirm trades and facilitate payment.
As Cross-Currency transactions may involve the simultaneous exchange of currencies, there is a risk that only one leg of the transaction may be completed, due to the possibility that parties use different systems in different countries that operate out of different time zones. This is known as cross-currency settlement risk, or Herstatt risk. Recently, foreign exchange dealers, encouraged by the BIS, have developed a number of practices to limit settlement risk. These measures include: firstly, banks now have strict limits on the amount of transactions they are willing to settle with a single counterparty on a given day. Secondly, banks have started to engage in a variety of netting arrangements, in which they agree to wire the net traded amounts only at the end of a trading day. Thirdly, settlement risk is eliminated if the exchange of the two monies occur simultaneously in a process known as payment versus payment (PvP).
More recently, we have witnessed the foundation of the Continuous Linked Settlement (CLS) Bank, which is owned by the world’s largest financial groups. CLS is the largest multi-currency cash settlement system, eliminating settlement risk for over half of the worlds foreign exchange payment instructions and its members include central banks, large commercial banks and other large corporations. The CLS daily settlement cycle operates with settlement and funding occurring during a five-hour window when all real time gross settlement systems are able to make and receive payments. This enables simultaneous settlement of the payments on both sides of a foreign exchange transaction. Each member holds a single multicurrency account with CLS, which has a zero balance at the start and the end of trading day. The settlement of the payment instructions and the associated payments are final and irrevocable.