Warning
I don't think it necessary but there are several links in this answer that are directly related to the horror movie Hellraiser. If you have issues with that type of content don't click on the links.
So it looks like what you are trying to make is a variation of the Movable Star Lament Configuration. I cannot seem to find any plans to reference or anyone that has done it will an accurate build process for this so it looks like we have to guess a little.
Still was does seen obvious is that we should be using 2 blocks to create this instead of one. A bandsaw, chisel, gouge and drill press appear to be the tools of choice for making this.
Make a template
First thing I would do is make a template on the computer and print them out several times for each face (4 assuming you don't have any oops moments.) You should be able to draw this out with a circle in the middle and a series of intersecting lines. It looks like the block is cut up into 16 equal parts. That gives us angles of 22.5 degrees. So with that in mind:

Then you could colour or mark the template to show what needs to be removed. The kerf of the blade should allow the to fit well if both blocks are cut from the same template
Circle
I think that you should cut the circle out first. Using a Forstner bit, like Steven suggests, would ensure you get a flat surface when you stop drilling. That's a lot of waste to clear out so make sure you clean out the hole as you progress (not while it is on of course).
The "interlock"
Once the circle is out then you can cut the alternating "keys". Clean up in between the keys with a chisel and the insides of the keys with a gouge to match the curve of the circle. Worry more about the faces that people will see more then the inside. Just like you see in this photo (before it was cleaned... presumably with a chisel):

(source: thekingofbelgium.com)
Image from The Puzzle Box Shop
An after thought would be you could still use the template and if the outside edges don't match up perfectly then you could just trim with the bandsaw to make it square.
Finishing side note
According to the site the where you pictures come from they put an ebony veneer on the end grain of that mahogany wood. Guessing that was done to help make a more uniform stain/finishing. The second set of blocks (candle holders maybe?) also look like they have a veneered top.