Power analysis to determine sample size depends on having estimates of the variability in what you're trying to measure and the magnitude of any differences that you're trying to find (often called "effect size"). Generic methods like those in your linked resource or implemented in software like G*Power take such estimates together with your desired significance levels and power to find the sample size for particular types of design. Yes, as you are evaluating paired comparisons instead of separate groups you would use corresponding paired instead of independent-group values for variability and effect size.
You seem, however, to have a fair amount of preliminary data on this. I thus suggest that you do your power calculation by simulating a large set of new values based on your preliminary data, trying your intended analysis on those simulated data, and seeing what sample size is needed based on your simulations of your particular situation.
That might seem daunting at first, but it's pretty straightforward. You already have information on test results and clinical annotations on many patients, the associated probabilities that clinicians versus the random forest (RF) would "prescribe" antibiotics or imaging, and the corresponding true findings of pneumonia. As those tend to be all-or-none decisions or results, each of those could be modeled with logistic regressions based on the data that you have. Next, you use those logistic-regression models to "predict" pneumonia and clinician versus RF-based recommendations for antibiotics and imaging for a very large number of "new patients" based on the distributions of clinical data among the patients in your population of interest. That gives you a set of simulated data. Then you perform your intended analyses on the simulated data, evaluating the sample size needed to detect the differences of interest.
This approach has a few advantages. First, instead of depending on crude generic estimates of variability and effect sizes you use estimates based on the data most directly related to your study: the data you already have. Second, it forces you to think carefully in advance about the statistical tests that you want to perform on your data. A crude power calculation with a generic tool might not end up working well for the specific test that you really want to perform. Third, through the simulation and analysis steps it forces you to think carefully about the nature of your data and the (potentially hidden) assumptions that you are making.
As you do this, however, I would recommend that you focus on probabilities instead of all-or-none classifications as much as possible. Although a clinician's decisions to prescribe antibiotics or order imaging are all-or-none decisions, those decisions are based on the clinician (perhaps unconsciously, or based on years of training and experience) putting together an estimate of the probability of a patient's having pneumonia with the costs and benefits of the drug or the imaging. Your RF presumably returns a probability of needing antibiotics or imaging; the probability cutoff that you choose for the RF implicitly represents those cost/benefit tradeoffs. Even your "ground truth" for antibiotics doesn't need to be all-or-none. If only 3 out of 5 clinicians think that antibiotics should have been prescribed in a case, maybe you should represent that as a 60% probability of needing antibiotics instead of a fixed "antibiotics-YES" decision.
Implementing the sampling from the data
As noted in a comment, you can't just sample from the marginal distributions of the patient characteristics separately, as they are highly correlated. One way to approach this problem would be to model those correlations directly and sample from the correlation model. A second would be to stick with the set of patients for which you already have clinical data but sample from their probability distributions of having pneumonia and needing antibiotics or imaging.
Modeling correlations among variables is often done with copulas. Copulas provide the link between the marginal distributions of individual predictors and their joint distributions. Recent work has shown how to extend methods originally focused on continuous joint distributions and parametric copula forms to mixed discrete and continuous distributions and to non-parametric copulas that might be needed for your data set.
A second approach, which might be simpler to implement, would be to extend your current data set to incorporate the variability in predictions from your model. For example, build a binomial model of pneumonia yes/no based on your current (pre-diagnosis) clinical data set. For each case in your data set, get the modeled probability of pneumonia. Make 100 copies of each patient's clinical data. Then label those copies as pneumonia yes/no in proportion to the modeled probability. For example, if the probability of pneumonia for a certain patient is 63%, label 63 of the patient's 100 data copies as pneumonia-yes and 37 as pneumonia-no.
That will give you an extended data set 100 times the scale of your current data set that incorporates your uncertainty in modeling pneumonia. Then you sample with replacement from that extended data set to evaluate the sample size needed for your study.
It sounds like you might be modeling all 3 outcomes of pneumonia, need for antibiotics, and need for imaging. If that's the case it might be best to model those all together in a multivariate binomial model that takes the inherent correlations among those outcomes into account. Then you would construct your extended data set in a way that incorporates those correlations among those outcomes. But the general principle would be the same.
The major point is that working with simulated data based on your current information is very fast, inexpensive, and flexible--particularly compared to what you would face if you rushed into an underpowered prospective trial based on a crude power estimate.
