Yes! Your mistake is trying to power a solenoid or a relay from the Arduino pin. Not possible. Use a transistor to switch the power to the solenoid or relay. Plenty of threads on how to do this can be found by using the search icon on the upper right of your forum page.
Why do you want to drive a solenoid with a relay? A solenoid is an electromagnetically operated device for moving something. A relay is some contacts moved by an electromagnet. Electrically a relay and a solenoid are the same. Whatever will drive a relay will drive a solenoid. Drive the solenoid directly with a FET.