Note: This answer was updated after we gained experience with issues for Windows Store Apps. Consequently, old comments in the question/answer might not make sense for new readers. 
WSA apps have a different API for file access, when compared with most other platforms. Like I mentioned in the question, each app has mostly only access to a local folder reserved for it (which thankfully includes the folder given by Application.persistentDataPath), and the API is async, and thus not supposed to block the application when files are being accessed. Unfortunately for us all as Unity developers, this seems to be the only way to get IO working in WSA, and the API is quite different to using System.IO classes.
First of all, Unity compiles code differently when building for the various platforms. When you simply select “Windows Store Apps” (WSA) as the active platform in Unity’s “Build Settings” window (not creating a build yet!) you’re still compiling scripts “as normal” in the Editor. This uses the Mono compiler, which is what Unity uses for most platforms. It means that, before actually being asked to build the application for WSA, Unity has no idea that many classes/methods might not exist in these apps, and also does not recognize classes which only exist there (as is the case with the Windows.Storage namespace), so everything seems to work as in the other platforms.
For actually building a WSA app, Unity uses a .NET compiler in your system (not Mono anymore), from a Windows Development Kit that you probably downloaded. This results in errors that you didn’t have before. In our case, we had a few errors with deprecated types (Hashtable, ArrayList, etc) and many errors with filesystem access (classes File, Directory, and our usage of full file paths related to BinaryReader, BinaryWriter, StreamReader, etc). The deprecated types are easy to solve, as there are clear generic substitutes (Dictionary, List, etc); the latter… not so much, as we are supposed to use the Windows.Storage namespace, which is full of async calls and totally different method calls.
Unity has a list of defines / preprocessor directives that you can use for dynamic compilation of script portions depending on the platform you’re building for. When you change the active platform to WSA (not building), Unity activates the UNITY_METRO directive, but I don’t find this one particularly useful. When you finally press “Build” for WSA, and Unity uses the .NET compiler, you have access to the NETFX_CORE directive. It’s only active when actually creating a build with the true .NET compiler, so you should wrap your WSA-only code with it, like so:
#if !NETFX_CORE
// code active when building for platforms other than WSA
System.IO.Directory.CreateDirectory(Application.persistentDataPath + "/UserData");
#else
// code active when building for WSA
/* <insert here some WSA-compatible code to create a directory> */
#endif
This compiles the “#if !NETFX_CORE” body when NOT building for WSA, with the usual method calls. Likewise, it compiles the “else” body in WSA builds, so any code put there will be able to access the Windows.Storage namespace. You might also need some of these “#if NETFX_CORE” when including libraries at the top of your script, so you might have, among others:
#if NETFX_CORE
using System.Threading.Tasks;
using Windows.Storage;
using Windows.Storage.Streams;
#endif
To solve our problem, we went to the trouble of learning the new API, creating a small library of methods implemented with the WSA API (just the ones we required) and filling our code with platform dependent compilation. It was hard but we got there. It was similar to what can be seen here (not my repository or my team’s!) and, more specifically, here. Also check their Whitepaper (.pdf) links in the project description, as they might be useful.
Later on, I actually further developed our code, so now there’s an asset for cross platform IO in the Unity Asset Store (shameless self-promotion! ;p). It’s called UnifiedIO, and contains quite a few common IO methods for handling files and directories in the same way for all platforms. Internally, it does platform dependent compilation like described here, allowing different implementations to be called depending on the platform.