Replacing an octagonal ceiling fan power outlet
Ceiling fans need to have listed Boxes NEC 314.27.C. If they are large ones there may be more hardware in the attic that you cannot access from below.
Lighter ones many times are screwed to a 2”x4” or 2”x6” that is screwed or nailed to the ceiling trusses. You may have to remove this brace to pull the box.