s:link serves to render a link to another JSF page, but using GET instead of POST (and therefore is an alternative to h:commandLink or a:commandLink, not to s:download).
s:download, on the other hand, renders a link to a resource served via the DocumentStoreServlet facility shipped with Seam (which is a way of exposing non-JSF resources, such as images or other content, without having to write a separate servlet). This tag allows you to serve non-static content with ease (otherwise you would need to create a custom servlet to provide the content).
s:download is not the only tag that uses the document store. s:graphicImage also uses the document store (it first places the image in the document store and then renders an img tag with the url of the document store in it), as do several other Seam tags.