I followed the instructions that I found in the documentation of the module, and everything worked absolutely perfect. The steps for your reference were:
- Enabled the modules: UR-API, UR-Mailer, UR-UI, UR-Views
- Created a new relationship (e.g. friend)
- In Permissions make sure that you have enabled the can have relationships permission in the user_relationships_api module (this is what I forgot the first time)
The rest of the permissions are pretty straight-forward. If you follow the instructions to the letter, you will get the link in the user profile page.
P.S: The guide in the above-mentioned link has a screenshot for the required permissions: make sure that your permissions match this screenshot's EXACTLY.
As for the block that you want to create:
Enable the UR-blocks module. It creates sample useful blocks (including a block for each relationship that you created). You can insert this block directly in the profile node using the corresponding tpl.php file and a code like the one that you can find in this article:
Drupal - How To Display Block In Node?