Be aware, # is not a special character, you do not need to escape it with %

The correct answer for your first question is lehtmi's, Using frontier pattern is the way to go, and yes it does work on latest 5.1 and luajit to make a match using string.match

string.match(str, "%f[^\n\r\0]###?[^#\r\n\0]+")

Should yield ##First line

How could I go about matching a pattern that starts with "line start" in Lua?

The simplest is to split the string into lines

for line in str:gmatch"[^\r\n]*[^\n]?" do
 if line:find"^###?.+" then -- stuff here
 end
end

Should be enough.