Hi Nick, I was able to get your paws glued on properly using the Trim and Join method instead of the booleans for this case, I've attached a 3DM file with the result.

This technique is something that can be used to get a result out of situations where the booleans are getting confused for some reason - in this case the booleans were most likely confused by the coincident surfaces not being identical, particularly with one's seam running through the middle of the area.

So to use Trim I went to the paw pieces and selected these faces here:



And then just deleted those faces to make those paw pieces be open surface fragments that look like this:



Then I separated out the upper surface of the main body piece that you want to connect them to, and selected that surface and ran the Edit > Trim command:



Then for the cutting objects I selected all the open edge curves of the paw pieces to use as cutting objects. That then cut the surface so it looked like this:



Then I glued all those pieces together back into a solid using Edit > Join to get the attached result.

One trick for the trim stage is that instead of picking all the little edge curves one by one in the stage where you're selecting cutting objects, you can use a script to do it with just one keystroke. To do that, go to Options > Shortcut keys, and add in a new shortcut key (I use N for "select naked edges"), and then for the command part paste in the script shown here:
http://kyticka.webzdarma.cz/3d/moi/#SelectNaked

That allows you to select "naked" edges (edges that only belong to 1 surface and are not joined between 2 surfaces) with the N key after that, it's a handy way to select cutting curves in a situation like this, and it's also very useful for analyzing which particular areas of an object are preventing it from being a closed solid object.

Hope this helps!

- Michael