Why are the functions failing to be called?

That's because they are nil.

Your script is being read left to right, top to bottom. Therefore when you call the function, the function doesn't exist yet because you haven't created it. You will actually never create it, since you put it after a while that will loop forever. Even though you type out the code, that code will never be read nor will it be executed.

Just create the function before you get sucked into an endless loop.

--Tab your code correctly!

local Playing = script:WaitForChild("Playing")
local Done = script:WaitForChild("Done")

function End()
	print('Game over')
end

function ReDo()
	print('Restarting')
end

while wait() do
	if Playing.Value == true then
		if Done.Value == true then
			End()
			wait(3)
			ReDo()
		end
	end
end

Might as well combine the if statements and shorten the conditions;

--Tab your code correctly!

local Playing = script:WaitForChild("Playing")
local Done = script:WaitForChild("Done")

function End()
	print('Game over')
end

function ReDo()
	print('Restarting')
end

while wait() do
	if Playing.Value and Done.Value then
		End()
		wait(3)
		ReDo()
	end
end