<p>Refractory high-entropy alloys (RHEAs) for extreme service environments require targeted mechanical property optimization. For this purpose, four NbMoTaWV-based RHEA/ceramic composites (undoped N, C-doped NC, 1 wt.% Al₂O₃-reinforced NCA-1, 5 wt.% Al₂O₃-reinforced NCA-5) were fabricated via mechanical alloying combined with rapid vacuum hot pressing. The effects of carbon doping and Al₂O₃ addition on phase composition, microstructure, and hardness were systematically investigated via multi-scale characterization and hardness testing, focusing on the synergy of multiple strengthening mechanisms. Results show that all samples possess ultrafine-grained structures in the nano- to submicron-scale. Carbon doping forms high-hardness W₂C and Mo₂C carbides, introducing significant precipitation strengthening. 1 wt.% Al₂O₃ refines and homogenizes grains, promotes the formation of a single (Ta,V)₂O₅ high-entropy ceramic phase, and achieves highly efficient strengthening synergy. Excessive Al₂O₃ causes local grain coarsening, breaking the synergistic balance and weakening the strengthening effect. Multi-scale hardness tests confirm the base N sample reaches 1473.19 HV; the NC sample achieves a 5.83% hardness increase; the optimal NCA-1 sample obtains a nearly 10% hardness improvement with a peak nanohardness of 24.558 GPa. The composition–microstructure–property correlation of the four RHEAs was revealed, and the addition of 1 wt.% Al₂O₃ was identified as the optimal parameter, and a reasonable design guidance for high-performance RHEA fabrication was introduced.</p>