Instance.new if clickdetector part is clicked?

Your code is correct and now next is,

1: Check Instance.new at http://wiki.roblox.com/index.php?title=Instance_(Data_Structure)

2: Your final script for Part (Key1)

local part = Instance.new("Part")
local script = game.ServerScriptService:FindFirstChild("ScriptPart")
local addscript = script:clone()
local oldpart = game.Workspace:FindFirstChild("Key1")

game.Workspace:FindFirstChild("Key1").ClickDetector.MouseClick:connect(function(playerWhoClicked)
playerWhoClicked.PlayerGui.Keys.Key2Found.Visible = true
wait(2)
playerWhoClicked.PlayerGui.Keys.Key1Found.Visible = false
wait(0.1)
game.Workspace:FindFirstChild("Key1").Transparency = 1

part.Anchored = true
part.BrickColor = BrickColor.new("Black")
part.Name = "Key2"
addscript.Parent = part
part.Parent = workspace

wait(1)
oldpart:Destroy()
end)

3: Other script for ServerScriptService (Key2)

local part = Instance.new("Part")
local script = game.ServerScriptService:FindFirstChild("ScriptPartKey3")
local addscript = script:clone()
local oldpart = game.Workspace:FindFirstChild("Key2")

game.Workspace:FindFirstChild("Key2").ClickDetector.MouseClick:connect(function(playerWhoClicked)
playerWhoClicked.PlayerGui.Keys.Key3Found.Visible = true
wait(2)
playerWhoClicked.PlayerGui.Keys.Key2Found.Visible = false
wait(0.1)
game.Workspace:FindFirstChild("Key2").Transparency = 1

part.Anchored = true
part.BrickColor = BrickColor.new("Black")
part.Name = "Key3"
addscript.Parent = part
Part.Parent = workspace

wait(1)
oldpart:Destroy()
end)

4: Other script again for ServerScriptService (Key3)

local part = Instance.new("Part")
local oldpart = game.Workspace:FindFirstChild("Key3")

game.Workspace:FindFirstChild("Key3").ClickDetector.MouseClick:connect(function(playerWhoClicked)
playerWhoClicked.PlayerGui.Keys.Key3Found.Visible = true
wait(2)
playerWhoClicked.PlayerGui.Keys.Key2Found.Visible = false
wait(0.1)
game.Workspace:FindFirstChild("Key3").Transparency = 1

end)

4: Copy final script in new script and your script in the part too, rename the both script "ScriptPart" and put it in ServerScriptService.

5: Copy 3rd script in ServerScriptService and rename it "ScriptPartKey3"

6: Make sure both script in ServerScriptService are disabled

Hi. If you want to create a new part, that is fairly simple.

local NewPart = Instance.new("Part", game.Workspace)
NewPart.Name = "PUT THE NAME YOU WANT IT TO BE CALLED HERE"

Now, if you want the part to appear in an exact position with an exact angle, you will want to edit it's CFrame. If you are not familiar with what CFrames are, they are the part's position AND angle within Roblox's 3D space. I would highly recommend looking in the wiki for how CFrames work.

Now, if you want this part to appear, look a certain way, have a click detector, and have a script inside of it, it is definitely possible to write a script that creates that. However, I believe it may be simpler for you if you create the part yourself in Roblox Studio, including everything that you want to be inside of it, position it exactly the way you want it, and then cut and paste it into ServerStorage. Then, at the end of your script, add

local NewPart = game:GetService("ServerStorage"):WaitForChild("WHATEVER YOU NAMED YOUR PART"):Clone()
NewPart.Parent = game.Workspace

...and you should be all set. Hopefully this helped. Let me know if you have more questions.

Oh, and as a side note, I would highly recommend adding some sort of debounce to your script so that players cannot just spawn tons and tons of your part.