Creating SOLID immutable and mutable Location types
It doesn't make sense to have setters in an immutable location.
Consider this alternative:

interface Location {
    int getX();
    int getY();
}

class MutableLocation implements Location {

    private int x;
    private int y;

    public MutableLocation(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public void adjustX(int x) {
        //adjust x
    }

    public void adjustY(int y) {
        //adjust y
    }
}

final class ImmutableLocation implements Location {
    private final Location location;

    public ImmutableLocation(int x, int y) {
        location = new MutableLocation(x, y);
    }

    @Override
    public int getX() {
        return location.getX();
    }

    @Override
    public int getY() {
        return location.getY();
    }
}


Your questions


  
  I'm not sure if the enum is an overkill
  


Not necessarily. Maybe it is, maybe it isn't. It will depend on the rest of the code in your project. From here it can go both ways.


  
  If the setters are a violation of SOLID; I'm not sure how else I should do it.
  


They violate SOLID, in particular the interface segregation principle:
the immutable class inherits setters but doesn't need them.
See my proposed cleaner alternatives above.


  
  If UnsupportedOperationException is best fit for the adjust method
  


For unsupported operations, this is fine, but your purpose is not clear.
Do you intend to add values in this enum without implementing adjust?
If yes, then your solution is fine.
But if you never intend to add values without implementing adjust,
then it would be better to make the method abstract.
Also you should use @Override in the implementations:

enum IncrementOperation {
    INCREASE {
        @Override
        public int adjust(int target, int amount) {
            return target + amount;
        }
    },
    DECREASE {
        @Override
        public int adjust(int target, int amount) {
            return target - amount;
        }
    };

    public abstract int adjust(int target, int amount);
}