I've got the exact same setup, a machine with Windows 8.1 and only Office 2013 installed. No trouble at all getting the Office 2007 PIAs installed. Do beware that this is a two-step process. After you downloaded PrimaryInteropAssembly.exe from the Microsoft server and started it, you prompts you to give a directory to store intermediate files. Navigate to that directory, right-click the o2007pia.msi
file and select Install to get them actually registered.
It isn't the only way to get them onto your machine. If you have another machine with the PIAs installed then create a dummy project and add the references to the Microsoft.Interop assemblies you need. Select them and ensure that the "Embed Interop Types" property is set to False and the "Copy Local" property is set to True. Build the project, you'll get the interop assemblies in the bin\Debug directory. Copy them to your machine and use the Browse button to add a reference to them. You always want the "Embed Interop Types" property set to True in your real project so you don't have to deploy the PIA on your user's machine anymore. Check them in with your project so you don't lose them again.
UPDATE: PIAs are obsolete since .NET 4.0 and VS2010. Check this post for the details.