Spoiler: no, there wasn't enough CPU power for a more complicated codec.
I had a Toshiba Libretto 30 with a 486 processor and PCMCIA soundcard. It could play MP3s .. but only with the Fraunhofer codec, Winamp required slightly more than 100% CPU.
That’s assuming you ran the codec on the CPU. We had codec-accelerator ASICs back then! MP3 players and DVD players were famously built on such ASICs. For a long time, the MPEG-2 decoder ASICs required for DVD playback were a differentiator on video cards and motherboards, allowing some PCs to offer DVD playback long before consumer CPUs were capable of realtime 480p MPEG-2 decoding. (E.g. the original iMac offered DVD playback through such an ASIC.)
The real questions in this hypothetical are:
1. if we handed the netlist for a modern H.265 codec ASIC to a 1990s fab, would they have been able to print it? (Maybe.)
2. Would the resulting chip have made H.265 a worthwhile encoding for shipping media in the 1990s? (Nah; the chip, as rendered at a ~100nm process node, probably would have been ridiculously power-hungry and hot. It would have worked out in a server with blower fans, or in a gaming PC with a powerful PSU and a water-cooling rig dedicated to the ASIC; but you couldn’t have put one in a piece of consumer electronics like the PlayStation 1. As such, its use, if anything, would only be studio-internal, maybe for archival storage of masters in a “nearly-losslessly-compressed” form.)
I had a Toshiba Libretto 30 with a 486 processor and PCMCIA soundcard. It could play MP3s .. but only with the Fraunhofer codec, Winamp required slightly more than 100% CPU.