We consider a base station (BS) that receives version update packets from multiple streams and broadcasts them using non-orthogonal multiple access (NOMA) over a fading broadcast channel. Sequentially indexed packets arrive randomly, rendering previous ones obsolete. The version age of information (VAoI) at a user is defined as the difference between the latest packet's version index at the BS and at the user. Our objective is to minimize the average VAoI across users, subject to an average power constraint at the BS, by optimally scheduling and transmitting packets with sufficient power for successful delivery. We consider channel-only stationary randomized policies (CO-SRP), making transmission decisions based on channel power gains, and obtain optimal CO-SRP, showing that VAoI achieved with CO-SRP is within twice the optimal VAoI. We also develop a Constrained Markov Decision Process (CMDP)-based solution, several heuristic benchmarks, and analyze CMDP policy properties. Simulations compare achievable VAoI and computational performance of various policies and reveal differences between optimizing AoI and VAoI. Notably, a scheme allowing transmission to at most one user at a time matches NOMA's performance under strict power constraints but is outperformed when constraints are relaxed. Additionally, AoI-optimized policies result in higher VAoI compared to VAoI-optimized policies and vice versa, when user arrival rates are mismatched.