UPDATE: I initially misunderstood the question. To learn how to create a service for the context menu in Safari, see part A of this answer. To learn how to create a service that takes no input and appears in the menubar > Safari > Services menu in Safari, see part B.

Part A: Creating a Contextual Text Service

Step 1

Follow part B's step 1 (I'll refer to it as B.1 from here on out).

Step 2

Follow B.2, but instead of selecting "no input," select "rich text."

In this case, you won't want to use anything else, because this is the step that makes it possible to see it from the contextual right-click menu when selecting text. This is because Automator requires some sort of input usually, and the type of input determines how it will get that input. If it's manual input, then it'll simply ask for the input when it runs, but if it's some sort of text that's already on the screen, it needs selected text to function. Note that you can't choose "URLs" because that does not mean that you can right click on URLs on the webpage, but that you can save the URL of the current page using the menubar. I chose "rich text" for this because it saves the text with its URL properties (i.e. you can click on it and it'll take you to the webpage once it's in the TextEdit document).

Step 3

As with B.3, write your workflow. In this case, it's really simple (there will be no download link because you can make it so easily):

In this case, all I'm doing is taking the input of the selected rich text as specified, and then copying it into a new TextEdit document, which should open up with the link once you've used the service.

Step 4

Finish things off by saving, as in B.4, and optionally do B.5 if you want to see where your services are located.

If you're looking to do something more advanced, like copying the URL from selected text, that would be more complicated, but feel free to experiment with it. You can always try URL shortening to create links, or perhaps have Automator open that webpage in a new tab and copy its URL as with the script in B.3.

Part B: Creating a Menubar URL Service

Step 1

First, you'll want to make sure that the workflow you created is a "Service" workflow. To do so, when you create a workflow, select the "Service" option like so:

Click on "Choose" and you're ready to create your service. You should see the typical Automator workflow builder window, as usual.

Step 2

Once you're there, make sure that you say your application is for Safari, using the menu at the top of the window. The other dropdown menu determines whether or not the Automator workflow takes any input. Depends on what you're doing, but in this case, I think you don't need any input, so select "no input."

Step 3

At that point, go ahead and build your workflow. It sounds like you already have a workflow you want to use, but here's one I built to do what you'd like:

At this point, you'll see that the service does not yet show up in the dropdown in Safari.

Step 4

In order to make it show up, make sure you've saved your Automator workflow.

The header on Automator should look like this:

If you check Safari now, your "Save URL" service should come up.

Step 5 (optional)

If you really want to check that your service was saved because it still isn't showing up in the menu, you can go to ~/Library/Services/ in Finder, where all workflows are stored. Keep in mind that the Library folder is hidden if you've never accessed it before. You can go here to find out how to view it and its contents.