How does Object (or ProtoObject) implement new?

It doesn't.  #new is a *class* method.  Box is a Class.
Printing "Box isKindOf: Class" => true.
More precisely, Box is an instance of (Box class) which
is a direct subclass of Class.

ProtoObject
  Object
    Behavior
      ClassDescription
        Class
          (Box class)

You'll find #new and #new: in Behaviour.
Behavior>>new
    <primitive 70>
    ^self basicNew

This means "run primitive number 70 in the VM.  If that fails,
return (self basicNew)."  It is normal to override #new, but not
to override #basicNew.  Let's look at that:

Behavior>>basicNew
    <primitive 70>	
    self isVariable ifTrue: [^self basicNew: 0].
    Smalltalk signalLowSpace.
    ^self basicNew.

To find out more, you'd have to look at primitive 70, which you might
think means fishing around in assembly code or C.  But no!  The Squeak
VM is written in (a subset of) Smalltalk, and you can look at
Interpreter>>primitiveNew in the Smalltalk browser!