Please read carefully again to see that it does not say that Time Machine is trying to back up to Macintosh HD.
It says that Time Machine could not back up the disk "Macintosh HD" (which is your iMac) because "it" (The Time Capsule disk) is nearly full.
The laptop backed up because that backup was much smaller than the other backup from the iMac.
The bottom line here is that the Time Capsule disk is very close to full and it is time to erase the drive and start over again with a new backup of each Mac and move forward. It will not be very long before you see the same message about the laptop not being able to back up because there is not enough space.
If you do not want to lose all of the old backups on the Time Capsule.....(even though you will likely never need them. Do you really need backups from many months and even years going back in time?)......it is possible to connect a USB hard drive to the back of the Time Capsule and use the Archive function in AirPort Utility to copy all of the data on the Time Capsule disk over to the USB disk......before....you erase the Time Capsule disk.
Now, if your Time Capsule is 6-7 years old, that is about the time that the Time Capsule hard drive and power supply tend to start acting up. So, I would not look at the Time Capsule as a long term backup solution if is the case.