Aaron, I think fax machines and paper were actually more secure than cloud computing. We used fax machines for decades and never experienced any security issues at all that I can remember. The data went to one receiving number, and unless your phone line was tapped, you were fairly sure no one else got the info. I have sent paper documents via mail or currier all my life, with never a problem.
The issue I have with the use of fax machines is that they are typically in a common area with easy access by pretty much anyone. They are easily readable, not encrypted (OK, some older machines tend to make them unreadable and appear encrypted!), there is no auditing on who accessed them and access controls are non-existent.
It also doesn't help that so much health data requires patients to recall pertinent data and to fill out multiple poorly copied forms. That data is image scanned and relies on either manual entry or optical character recognition -- neither of which are very accurate. Manual data entry is still poor in healthcare with data not stored very discretely (separated into discrete or individual fields). So much data is still stored in a notes area as free-form text. As long as it can be printed, then it's considered adequate.
While paper is no longer stored physically, most paper exists electronically as scanned images. I have seen so many times where documents were generated and printed only to be turned around and scanned then shredded. It's an issue where healthcare still hasn't let go of the paper process. It's better than it was, but still has a long way to go.
As for your credit card experience, much of that derived from poor personnel control. It was too easy for a clerk to copy the information necessary to use the card. That has largely been mitigated by the use of self-service card swipes and chip technology. My card got hijacked once a few years ago and I was able to trace it to the store where I used it. USAA was awesome about how they investigated and handled the situation.