Just in case people are trying to port their own stuff and are finding this thread via Google or something, I've since been able to successfully port the whole thing to be used in Metro. Some things I had to find some other way for (I needed the assembly's major version, but I just made it a hardcoded const int now, and I still don't know how to set the Date header in a HttpWebRequest but fortunately the webservice I was using provided an alternative, and I'm not catching ProtocolError WebExceptions anymore). Other things were easier: Array.ConvertAll was replaced by a LINQ query and a foreach, String.ToLower(IFormatProvider) was replaced by String.ToLowerInvariant(), and NameValueCollection was replaced by Dictionary<string, string>. Instead of HttpUtility.UrlEncode I used Uri.EscapeUriString, which is apparently a better way of doing it even if you're just writing regular, non-WinRT applications.
Replacing the HMACSHA256 class proved the most difficult, but I've figured it out using the Windows.Security.Cryptography namespaces. Basically to hash a string message using a key, you do
string stringToSign = "Whatever message you wish to sign";
string hashKey = "The key you want to sign it with."
MacAlgorithmProvider macAlgorithmProvider = MacAlgorithmProvider.OpenAlgorithm("HMAC_SHA256");
BinaryStringEncoding encoding = BinaryStringEncoding.Utf8;
var messageBuffer = CryptographicBuffer.ConvertStringToBinary(stringToSign, encoding);
IBuffer keyBuffer = CryptographicBuffer.ConvertStringToBinary(hashKey, encoding);
CryptographicKey hmacKey = macAlgorithmProvider.CreateKey(keyBuffer);
IBuffer signedMessage = CryptographicEngine.Sign(hmacKey, messageBuffer);
string hashedString = CryptographicBuffer.EncodeToBase64String(signedMessage);
Basically you create a MacAlgorithmProvider and tell it what algorithm you want to use (since I was using HMACSHA256 I told it to use the HMAC_SHA256 algorithm), you create IBuffers that you fill with the binary values for your message and hash key, tell the algorithm provider to create a CryptoGraphicKey using the IBuffer you made from your hash key string, and then call CryptoGraphicEngine.Sign to sign your stuff. Then to convert it back to a regular string you simply call CryptographicBuffer.EncodeToBase64String().