I don't remember the K6-2 being made at 500MHz, unless it was a K6-2+ processor. The K6-2+ or K6-3 will beat the Celeron at that MHz range for speed in most apps, due to cache architecture (a 500MHz Celeron has 128kb cache, but the architecture differences make the K6 faster), however the K6 class CPU will run hotter, so make sure you have a quality heatsink/fan for the CPU. With a good quality heatsink/fan, they'll run just fine. On the other hand, the Celeron might be more upgradeable in the future, as the K6 class tops out at around 500-550MHz, and the Celeron goes higher. The Celeron also does better floating point, so math-based apps and some games will run faster on it.
Also check the mainboard differences. Either CPU could be hampered by a crappy PCChips or SiS chipset based mainboard, moreso if that mainboard also provides the video. An inexpensive graphics card, like a used ATI or Matrox 8MB could make a world of difference.
Check on the RAM. I'm assuming both systems use SDRAM, but that may not be the case with the occasional K6 system, some mainboards managed to combine both SIMM and DIMM sockets, thus making for very poor memory performance.
P.S. For slightly more, you could probably build an AMD Duron or Intel P3 or Celeron system in the 1GHz range that would blow the doors of these two systems. It's worth doing if you know how to shop Ebay. The system I built for my wife five months ago consists of the following:
Case - gotten for free from a friend
Power Supply - lying in my spares pile
1GHz Celeron (Tualatin Core) - $40 on Ebay, new retail box
Mainboard - MSI Intel i815 chipset with onboard LAN and sound, $40 on Ebay, new retail box
ATI Radeon 7000 32MB AGP and 256MB SDRAM DIMM -bought in a combo off of Ebay for $35 for the pair
40GB WD Caviar SE hard disk - $60 at NewEgg.com
I put in a SCSI CD-ROM, CDRW, and controller that I had lying around,
and because the case had a special spot for one, an IDE Zip drive I had sitting idle too. I got her a 17" monitor free from her dad when he decided to let me help him buy a 19" one. I also got another 256MB memory module from somewhere else in trade, and stuck that in too. It runs Windows XP great and she loves it.
Intel Q9450 @3.2GHz, Gigabyte GA EP45-UD3P, 4 x 2GB G.Skill @4-4-4-12
Antec P160SW case (modded), Xigmatek 750w PSU
3x 500GB (RAID-5), , OptiArc 7200S, ASUS E818A3T
Creative X-Fi XtremeGamer, Hauppauge HVR-1800, Radeon 4890