It took 4 steps to decrypt the key.
Step 1: Get the link decrypted. The link was a shift-5(ROT5) on a Caesar Cipher. The link was
http://pastebin.com/kbkdv49r
Step 2: The code was binary encoded into hex. Decode the code to binary. Which brings us to the next step.
Step 3: Decode the binary to text. To then get this:
Code:
uanrcsfuwlluoyd! zqrp tk kofc cqy:
6747-m972-1864-qx43
Step 4: The message was encrypted using a Vigenere Cipher. The Vigenere Cipher requires a key, the key was in the pastebin. "There is another key to unlock the puzzle, although
small it is, it is not hard to find.". The key was small(hehe). Using the key "small", you can then process the cipher-text using any ol' vigenere cipher decryptor and successfully retrieve the key. The only part remaining would to make the 3 letters in the key capital letters.
I think you didn't capitalize the key.