It's actually there, though a search from the store's search field doesn't show it. The description says "VLC for Windows 8 is an experimental port of VLC media player for the WinRT platform." It should be compatible even if the listed processors don't say so because Modern UI apps are supposed to be cross-compatible on Windows RT (ARM) and otherwise.
Make sure you're on your Surface and open Jeff's link in IE (I used metro IE) and it'll open the store automatically.
That said, I can't install it due to an
0x80240017 error.
Where the fix, according to Microsoft's KB, should have been installed in a November 2013 rollup, and my Surface is up to date, so who knows.