Can RSA signing be implemented on top of RSA encryption/decryption? I need to use RSA-SHA256 signing. Unfortunately not all Microsoft CryptoAPI providers support that. It's possible that I might get a handle to a CryptoAPI provider that can just encrypt/decrypt with RSA, and maybe sign with SHA1, but not SHA256. Also, the private key might be unavailable (say, it could be in a smart card or some such device).

Is it then possible for me to "fill the gaps" myself? I can, after all, calculate the SHA256 hash of the data myself. Can I then somehow encrypt it with the provider and get a valid signature? Simply encrypting the hash doesn't seem to work (it produces the wrong result).

Or is the signing algorithm a modification of the encryption algorithm, and if the provider doesn't support it, then there's physically nothing that I can do?
Yes, you can, but you would need access to raw or textbook RSA encryption and you would have to implement the PKCS#1 v1.5 or PSS padding primitives yourself. Beware that PKCS#1 v1.5 compatible padding is different for encryption signature generation.

If you only have PKCS#1 v1.5 encryption or OAEP encryption available then the encryption routine will already pad your data, and in that case you cannot use the encryption API to sign.

The padding methods in common use are found in RFC 3447 which basically is a copy of RSA/EMC's PKCS#1 v2.1 specification.