I ended up implementing the following solution. It appears to work for my use case.

package com.example;

import org.apache.commons.lang.StringUtils;
import org.nuxeo.ecm.automation.core.Constants;
import org.nuxeo.ecm.automation.core.annotations.Context;
import org.nuxeo.ecm.automation.core.annotations.Operation;
import org.nuxeo.ecm.automation.core.annotations.OperationMethod;
import org.nuxeo.ecm.automation.core.annotations.Param;
import org.nuxeo.ecm.core.api.ClientException;
import org.nuxeo.ecm.core.api.CoreSession;
import org.nuxeo.ecm.core.api.DocumentModel;
import org.nuxeo.ecm.core.api.DocumentModelList;
import org.nuxeo.ecm.core.api.impl.DocumentModelListImpl;
import org.nuxeo.ecm.platform.relations.api.Graph;
import org.nuxeo.ecm.platform.relations.api.Node;
import org.nuxeo.ecm.platform.relations.api.QNameResource;
import org.nuxeo.ecm.platform.relations.api.RelationManager;
import org.nuxeo.ecm.platform.relations.api.Resource;
import org.nuxeo.ecm.platform.relations.api.ResourceAdapter;
import org.nuxeo.ecm.platform.relations.api.Statement;
import org.nuxeo.ecm.platform.relations.api.impl.ResourceImpl;
import org.nuxeo.ecm.platform.relations.api.util.RelationConstants;

import java.util.Collections;
import java.util.List;
import java.util.Map;

@Operation(id = GetAllLinkedDocuments.ID, category = Constants.CAT_SERVICES, label = "Get All Linked Documents", description = "Get all documents related to the input document.  Includes the input document and any linked documents found via recursive relation search.")
public class GetAllLinkedDocuments {
    public static final String ID = "Example.Document.GetAllLinkedDocuments";

    @Context
    protected CoreSession session;

    @Context
    protected RelationManager relations;

    @Param(name = "predicate")
    protected String predicate;

    @Param(name = "graphName", required = false)
    protected String graphName;

    @OperationMethod
    public DocumentModelList run(DocumentModel doc) throws Exception {
        Resource pred = new ResourceImpl(predicate);
        Graph graph = relations.getGraphByName(getGraphName());
        DocumentModelList result = new DocumentModelListImpl();
        depthFirstSearch(graph, pred, doc, result);
        return result;
    }

    private void depthFirstSearch(Graph graph, Resource pred,
                                  DocumentModel doc,
                                  DocumentModelList found) {
        found.add(doc);
        for (DocumentModel relatedDoc : getRelatedDocs(graph, pred, doc)) {
            if (!found.contains(relatedDoc)) {
                depthFirstSearch(graph, pred, relatedDoc, found);
            }
        }
    }

    private DocumentModelList getRelatedDocs(Graph graph, Resource pred,
                                             DocumentModel doc) {
        QNameResource resource = (QNameResource) relations.getResource(
                RelationConstants.DOCUMENT_NAMESPACE, doc, null);
        List<Statement> statements = graph.getStatements(resource, pred, null);
        DocumentModelList docs = new DocumentModelListImpl(statements.size());
        for (Statement st : statements) {
            DocumentModel dm = getDocumentModel(st.getObject());
            if (dm != null) {
                docs.add(dm);
            }
        }
        return docs;
    }

    // copied from org.nuxeo.ecm.automation.core.operations.services.GetRelations
    protected DocumentModel getDocumentModel(Node node) throws
            ClientException {
        if (node.isQNameResource()) {
            QNameResource resource = (QNameResource) node;
            Map<String, Object> context = Collections.<String, Object> singletonMap(
                    ResourceAdapter.CORE_SESSION_CONTEXT_KEY, session);
            Object o = relations.getResourceRepresentation(
                    resource.getNamespace(), resource, context);
            if (o instanceof DocumentModel) {
                return (DocumentModel) o;
            }
        }
        return null;
    }

    // copied from org.nuxeo.ecm.automation.core.operations.services.GetRelation
    public String getGraphName() {
        if (StringUtils.isEmpty(graphName)) {
            return RelationConstants.GRAPH_NAME;
        }
        return graphName;
    }

}

Instead of creating getRelatedDocs and copying the methods getDocumentModel and getGraphName, why not use the corresponding operation (Relations.GetRelations) ? Is there any performance issue?

For example, something like this (not tested):

private void depthFirstSearch(Graph graph, Resource pred,
                              DocumentModel doc,
                              DocumentModelList found) {

    OperationContext ctx = new OperationContext(session);
    ctx.setInput(doc);

    Map<String, Object> params = new HashMap<String, Object>();
    params.put("predicate", "http://purl.org/dc/terms/References");
    params.put("outgoing", true);

    AutomationService service = Framework.getService(AutomationService.class);

    found.add(doc);
    for (DocumentModel relatedDoc : (DocumentModelList)service.run(ctx, "Relations.GetRelations", params)) {
        if (!found.contains(relatedDoc)) {
            depthFirstSearch(graph, pred, relatedDoc, found);
        }
    }
}