How does Foo::Bar::Builder and Foo::Bar::Store know, that there is a Foo::Bar or better what Foo::Bar is!

The .pm files that use XSLoader or Dynaloader or whatever you use to load and initialize the shared library of XSUBs can use the other modules.

... how do i call the new function of Foo::Bar (defined in Foo/Bar.xs) inside Foo/Bar/Builder.xs?

Assuming you've already loaded the other shared libraries in your .pm file, they look just like normal Perl subroutines, so call them as normal.