Since 32-bit dlls can't be loaded into a 64-bit process Paint.NET can not use the 32-bit plugins, as Photoshop only went 64-bit in CS4 the list of 64-bit plugins is rather limited.
The solution here is to use a surrogate process. Paint.NET's 64-bit process talks to a separate 32-bit process that in turn loads all the plugins.
As for the search directories searching the Paint.NET Effects directory would work, searching the Photoshop plug-in directory seems pointless as the filters installed with photoshop would most likely not run (unless perhaps if you are running Photoshop 3.0 ).
It's not for the filters installed with Photoshop, it's for the filters someone with Photoshop has installed. It makes sense that someone who installed a filter into Photoshop would want to be able to use the same one in Paint.NET without installing it in multiple locations.
Integrating with the menu system is tricky as the plugin systems are so different, and I see no easy way to do this.
This is indeed tricky, not because the plugin systems are different, but because Paint.NET polls its plugins for a list of Effect-derived types at startup to populate the Effects menu. I can help you with this - the solution requires getting messy with C++/CLI or IL(D)ASM.