A new D-shaped tellurite photonic crystal fiber sensor based on the four-wave mixing (FWM) effect with the surface plasmon resonance (SPR) effect is designed and optimized. The substrate of the D-shaped photonic crystal fiber (D-PCF) is tellurite glass, and the polished surface is plated with the gold film and hydrogen gas-sensitive film. An air hole of the inner cladding, which is plated with the gold film and methane gas-sensitive film, is selected as the second sensing channel to simultaneously measure the concentration of hydrogen and methane. Based on the four-wave mixing, the wavelength shifts of the Stokes and anti-Stokes spectra resulting from the variation of the gas concentration can be used to accurately detect the concentrations of methane and hydrogen. Meanwhile, it is found that the SPR effect can increase the wavelength shifts, which means the sensitivity of methane and hydrogen augment. After parameter optimization, the maximum sensitivities of methane and hydrogen are 4.03 nm/% and -14.19 nm/%, respectively. Both the linearities are up to 99.9%. The resolution of methane is 1.25×10-2% and hydrogen is 7.14×10-3%. Moreover, the fiber length of this sensor is only 20 mm, which is conducive to the construction of a compact or ultra-compact embedded FWM fiber sensor.