PHP AES-256 CBC faster than AES-128 CBC?
I'll answer in order:


No, you may not be doing something wrong. This is just the compiler warming up and performing optimizations. The second run you see that AES-128 is already about as fast, which is what you would expect (it should be ever so slightly faster in the end, but that might not even be noticeable).
Don't know, you'd have to debug, because that's certainly wrong.
The key should not be in any kind of encoding. The key used by OpenSSL should consist of bytes indistinguishable from random. You can use hexadecimals for storing keys in string (something that's rather questionable as well) but you should decode it before using it. 
Same as for the encryption key; you'd use openssl_random_pseudo_bytes or another secure random number generator. Then you may encode it to hexadecimals or base 64, as long as you decode it again to binary before you use it.


Note that if you provide a 16 byte key as 32 hexadecimals that you might be using AES-256 without realizing it yourself. Best test against another framework / crypto library (but NOT mcrypt).



You should not store your users passwords encrypted. Instead you should use a password hash such as bcrypt.