I have created a rectangle, then converted it into an editable poly. Then I created a circle and converted it to editable poly too. How to make it so that that the circle becomes a hole in the rectangle?
That's called a Boolean operation. You can find a video tutorial here for almost the exact situation you're asking about.
Essentially, it looks like you create a new object with your two objects selected. You'll likely need to make your circle a cylinder first. The new object is a Compound Object of type Boolean. Then in the operations you select A-B (where A is your rectangle and B is your cylinder).
It's still a boolean operation. It's just done with splines that share a common plane. Check the Boolean heading on this page.
If you don't want to use booleans...
Obviously this creates a square hole. However, if you add more verts around the edges of the cube before using INSET, you could later manually shape the hole.