Those literal descendants of Abraham well knew the Hebrew scriptures where God is stated to have 'fathered' the nation of Israel. Here is a sample:
Israel "forsook God which made him, and lightly esteemed the Rock of
his salvation... Of the Rock that begat thee thou are unmindful, and
hast forgotten God that formed thee." (Deuteronomy 32:15 & 18)
"Wherefore David blessed the Lord before all the congregation: and
David said, Blessed be thou, Lord God of Israel our Father, for ever
and ever." (1 Chronicles 29:10)
"He shall cry unto me, Thou art my Father, my God, and the rock of my
salvation." (Psalm 89:26)
"For he said, Surely they are my people, children that will not lie:
so he was their Saviour... But they rebelled..." and Isaiah replies,
"Doubtless thou art our Father, though Abraham be ignorant of us, and
Israel acknowledge us not. Thou, O Lord, art our Father, our redeemer,
thy name is from everlasting." (Isaiah 63:8-10 & 16)
"A son honoureth his father, and a servant his master: if then I be a
Father, where is mine honour? And if I be a master, where is my fear?
saith the Lord of hosts unto you, O priests, that despise my name."
(Malachi 1:6)
That is the background which enables readers of this exchange between Jesus and the religious leaders in Jerusalem to understand what the point was. As literal descendants of Abraham, and as part of the nation of Israel that came from Abraham, they knew and believed that God was their ultimate Father, who 'birthed' the nation of Israel back in Egypt. God formed the nation of Israel, to honour his promise to Abraham, and to make a people for his own name's sake.
So, both senses of fatherhood are correct, which is why Jesus did not find any fault with the premise, but he did find fault with those who claimed to have God as their Father, but who did not honour and fear him as they should. Why, they were seeking to put to death the only-begotten Son of God standing in front of them!
When those ones who hated Jesus spoke of not being born of adultery, they were making a snide reference to their belief that Jesus had been born out of wedlock (which wasn't true, but they so hated Jesus, they preferred to believe lies rather than acknowledge his legitimate line of earthly descent.)
That is why Jesus denied their claim to have God as their Father, telling them that they were of their father, the Devil, who was a murderer and a liar from the beginning (John 8:44) They sought to murder Jesus because they would not believe the truth from God that he was telling them. Thus, there is no contradiction.