@Mark. Let me try to clarify the confusion points that you have.

Definition of Exp

The definition of Exp that we are assumming in page 10 is:

interface Exp {
    Value eval();
}

which is presented earlier in the paper in Figure 1. The alternative version of Exp with visitors can be ignored. We used it merely to talk about visitors and the relationship with Object Algebras, and it does not play a role in later parts of the paper.

Also, regarding the code in page 8, I think there is a typo in the paper. You are right: it seems that there we were assuming an eval method that returns int. When we were writing the paper we were using multiple versions of Exp, and probably we used the code for another version there by mistake. The code in page 8, adapted to the representation in the paper, should be:

int x = exp(base).eval().getInt();

The Choices for Value

The code that we intended to have for the implementation of the Value class uses exceptions, similarly to your own attempt, and it is indeed partial as presented in the paper. In the paper, the point that we were making is about the extensibility and type-safety with respect to the source expressions. For the values, all we wanted was that values were rich enough to support the source expressions, and the assumption was that the values themselves were not extensible (later in Section 7 we briefly discuss extensible values). The representation that we choose in the paper was aimed at keeping the code simple, and avoid some distractions with dealing with error management (which are orthogonal to extensibility).

Agreeably this is not a great representation but, at least with the Java version at the time, it seemed like a reasonable compromise. In modern Java, I think the way to go would be to have Value modelled as an algebraic datatype. Java 16 supports pattern matching and sealed types, which can be used to essentially model algebraic datatypes in functional programming. So you could model Value with something like:

sealed interface Value {}
record VInt(int x) implements Value {}
record VBool(boolean b) implements Value {} 

In retrospect, to avoid confusions like the one you're having, I think it would have been better to have presented the paper simply using the interface:

interface Exp {
    int eval();
}

and to use an if construct à la C, where integers play the role of booleans. This would have avoided distractions with the representation of Value in the first place.

The Representation of Values in the Paper

In any case, getting back to the representation of the paper, and also to your point about partiality, I show a minimal, but complete implementation of the code next. For illustrating that partiality is not a fundamental issue, I also switch from using unchecked exceptions to checked exceptions.

First we can define values as follows:

interface Value {
    // You can choose checked exceptions or unchecked exceptions.
    // In the paper we opted for unchecked exceptions.
    // But here, I show that you can also use checked exceptions,
    // if you want to ensure that you deal with exception cases.
    int intValue() throws Exception;
    boolean boolValue() throws Exception;
}

class VInt implements Value {
    int x;

    public VInt(int x) {
        this.x = x;
    }

    public int intValue() throws Exception {
        return x;
    }

    public boolean boolValue() throws Exception {
        throw new Exception();
    }

    public String toString() {
        return Integer.valueOf(x).toString();
    }
}

class VBool implements Value {
    boolean b;

    public VBool(boolean b) {
        this.b = b;
    }

    public int intValue() throws Exception {
        throw new Exception();
    }

    public boolean boolValue() throws Exception {
        return b;
    }

    public String toString() {
        return Boolean.valueOf(b).toString();
    }
}

Then you can write the code with for Object Algebras as follows:

    // Integer Expressions
interface IntAlg<Exp> {
    Exp lit(int x);
    Exp add(Exp e1, Exp e2);
}

interface Exp {
    Value eval() throws Exception;
}

class IntEval implements IntAlg<Exp> {
    public Exp lit(int x) {
        return () -> new VInt(x);
    }

    public Exp add(Exp e1, Exp e2) {
        return () -> new VInt(e1.eval().intValue() + e2.eval().intValue());
    }
}

// Boolean Expressions
interface BoolAlg<Exp> extends IntAlg<Exp> {
    Exp bool(boolean b);
    Exp iff(Exp e1, Exp e2, Exp e3);
}

class BoolEval extends IntEval implements BoolAlg<Exp> {
    public Exp bool(boolean b) {
        return () -> new VBool(b);
    }

    public Exp iff(Exp e1, Exp e2, Exp e3) {
        return () -> e1.eval().boolValue() ? e2.eval() : e3.eval();
    }
}

public class Main {
    public static <Exp> Exp m(IntAlg<Exp> alg) {
        return alg.add(alg.lit(4),alg.lit(3));
    }

    public static <Exp> Exp m2(BoolAlg<Exp> alg) {
        return alg.iff(alg.bool(false),m(alg),alg.bool(true));
    }

    public static void main(String[] args) {
        Exp e = m(new IntEval());
        try {
            System.out.println(e.eval());
        } catch (Exception exp) {
            System.out.println("Ops! There is an error...");
        }

        Exp e2 = m2(new BoolEval());
        try {
            System.out.println(e2.eval());
        } catch (Exception exp) {
            System.out.println("Ops! There is an error...");
        }
    }
}

As you can see in the definition of the main, we need to eventually deal with the exceptions. As a matter of fact, if you wanted to deal more nicely with errors, you should change the code in the interpreter to catch the exceptions there, and then give error messages like "You cannot add a boolean to an integer..." and so on. That does involve extra code (which is not so related to the main point of the technique), but it can be easily done.

Also note that I'm using lambdas to avoid some boilerplate with anonymous classes. In Java anonymous classes with a single method implementation can be written as a lambda.

If you do not like code using exceptions, and you'd prefer a more functional-style approach, you could also use Java's Optional class to model failure (just as you'd do in a functional language like Haskell, say). In such case, you could have the following:

// Values
interface Value {
    Optional<Integer> intValue();
    Optional<Boolean> boolValue();
} 

// The expression interface
interface Exp {
    Optional<Value> eval();
}

Where we now use Optional instead of making the operations partial. The Java code (without pattern matching) with this option will not be so nice, but maybe with the new pattern matching features it won't be that bad.