Why can't I encrypt web.config/appSettings using a custom configProtectionProvider on Azure (Windows Server 2012)?
Did you attempt installing the assembly in the GAC yet on role start?
Information on adding assemblies to the gac on start up http://blogs.infosupport.com/adding-assemblies-to-the-gac-in-windows-azure/
I was able to fix this error by installing the NuGet package: https://www.nuget.org/packages/Pkcs12ProtectedConfigurationProvider/
I'm guessing part of the install process is registering the .dll for you.