I can personally confirm that every install of Red Star OS comes with Tetris (kBlocks), Atomix (kAtomic), and Minesweeper (kMines). So, they've got Tetris at least.
There's also a package manager to download more games if you have access to Kwangmyong, the national intranet. There's access at libraries, universities, internet cafes, parts of Pyongyang have Wi-Fi too. I think all the KDE Games are available, but I'm not actually sure if they allow the Card, Arcade, or Tactics & Strategy titles. The board games and logic games for sure are.
Arirang phones come with a bootleg of angry birds and a modded copy of Plants vs Zombies, but no Tetris.