I tried entering my Father's details into the search box at FamilySearch but it didn't come up with a match.
That's incorrect. You need to search using 'exact match' (check the checkboxes underneath the names):
familysearch.org/ark:/61903/1:1:QVZ4-YKW8
familysearch.org/ark:/61903/1:1:QVDW-4DKN
familysearch.org/pal:/MM9.1.1/QVDW-QDQH
Once you have access to the original documents, you should be able to find out the names and birth dates of your grandparents and (probably) great grandparents.