First of all, this seems to be a well designed system, with well formatted code and well named variables, that is easy to parse. I don't see anything inherently wrong, but of course there are optimizations possible.

CodeBuilder

This seems to mimic the functionality of ByteBuffer. It seems easier to just use ByteBuffer.allocate(capacity) as you will get all functionality for free, and it is well described. You can move it to a read-only byte-buffer after building it. It can also be used to encode / decode strings.

     void emit(String str, int startIndex) {
        byte[] stringBytes = str.getBytes();

        for (int i = 0; i < stringBytes.length; ++i) {
            code[startIndex + i] = stringBytes[i];
        }
    }

First of all it isn't clear why you've chosen to disregard position here, this does not follow the principle of least surprise. Besides the already mentioned str.getBytes() issue that doesn't indicate the CharSet / uses platform default, the other issue is that you've chosen to use a convenience method. It would take some more code, but you could directly encode to your bytes using a CharsetEncoder in the Java NIO package.

Same goes for the PrintStringInstructionImplementation. This may not be important for a nice little test machine, but in the end one should try and perform a minimum of copying. And you'd use the best function available such as System.arraycopy when you do need to copy e.g. bytes (but maybe it is part of the assignment not to use functions to implement the machine?).

            machine.checkTapeReserve(1);

This function seems to be called every time and it is during execution. I'd just have the class return the size (depending on the instruction, the parameters and possibly the size) and have the caller execute test if the "tape reserve" is sufficient before calling the execution. You could have a default implementation in the interface that returns 1.

Having classes return this kind of information will also help during runtime with debugging and the generation of descriptive errors.

I'm not 100% on using the name "tape" here, but as it is a well known concept in PL design, I guess it's OK.

Same goes for machine.advanceInstructionPointer(); I guess.

    /**
     * Delegates to the pop operation.
     */
    public static final class ConstInstructionImplementation 
            extends PushInstructionImplementation {

Spot the documentation issue :). It is not clear why this class exists; that should be documented instead.

    public static final class AddInstructionImplementation 
            extends BinaryArithmeticInstructionImplementation {

        public AddInstructionImplementation() {
            super((n1, n2) -> { return n1 + n2; });
        }
    }

Extreme nitpick: this is a binary arithmetic op, i.e. an operation on two operands, but I would at least put in a comment that this is different from a bitop.

        public ModuloInstructionImplementation() {
            super((n1, n2) -> { return n1 % n2; });
        }

Java calls this the remainder operator, not the modulus operator. Because it implements a remainder function :p

For some reason the instruction pointer is always advanced before executing the function. This may make traces harder to handle.

It is kind of weird to perform that operation before e.g. an Unconditional Jump - one of the reasons of not advancing the instruction automatically outside of the execution is to make sure that jumps are handled correctly, but here the fact that the jumps changes the instruction pointer anyway is ignored.

Map<String, Operation> mapOperationByteToOperationEnum ...

Not incorrect, but with 256 bytes it would be much faster to create an Operation[256] array (or ArrayList if you want to use some specific class for some reason) and then use that to map to operations. Hashing an integer in the range 0..256 is not fast. You can simply not fill the locations in the array if not mapped, so they stay set to null.

Not a big issue for testing your design and this array can be build externally from the enum of course.