Connecting vertices in different objects
As you correctly suspected, you can only create faces with vertices of the same object. Join the objects first, by selecting them in Object Mode and pressing CtrlJ. Then create the face by selecting the vertices and pressing F.