Oxygen and methane are considered to be the canonical biosignatures of modern Earth, and the simultaneous detection of these gases in a planetary atmosphere is an especially strong biosignature. However, these gases may be challenging to detect together in the planetary atmospheres because photochemical oxygen radicals destroy methane. Previous work has shown that the photochemical lifetime of methane in oxygenated atmospheres is longer around M dwarfs, but M dwarf planet habitability may be hindered by extreme stellar activity and evolution. Here, we use a 1D photochemical-climate model to show that K dwarf stars also offer a longer photochemical lifetime of methane in the presence of oxygen compared to G dwarfs. For example, we show that a planet orbiting a K6V star can support about an order of magnitude more methane in its atmosphere compared to an equivalent planet orbiting a G2V star. In the reflected-light spectra of worlds orbiting K dwarf stars, strong oxygen and methane features could be observed at visible and near-infrared wavelengths. Because K dwarfs are dimmer than G dwarfs, they offer a better planet-star contrast ratio, enhancing the signal-to-noise ratio (S/N) possible in a given observation. For instance, a 50 hr observation of a planet at 7 pc with a 15 m telescope yields S/N = 9.2 near 1 m for a planet orbiting a solar-type G2V star, and S/N = 20 for the same planet orbiting a K6V star. In particular, nearby mid-late K dwarfs such as 61 Cyg A/B, Epsilon Indi, Groombridge 1618, and HD 156026 may be excellent targets for future biosignature searches.