Why am I able to use Kernel singleton methods like `puts`?

You are looking in the wrong place.

Methods like Kernel#Array, Kernel#Complex, Kernel#Float, Kernel#Hash, Kernel#Integer, Kernel#Rational, Kernel#String, Kernel#__callee__, Kernel#__dir__, Kernel#__method__, Kernel#`, Kernel#abort, Kernel#at_exit, Kernel#autoload, Kernel#autoload?, Kernel#binding, Kernel#block_given?, Kernel#callcc, Kernel#caller, Kernel#caller_locations, Kernel#catch, Kernel#eval, Kernel#exec, Kernel#exit, Kernel#exit!, Kernel#fail, Kernel#fork, Kernel#format, Kernel#gets, Kernel#global_variables, Kernel#initialize_clone, Kernel#initialize_copy, Kernel#initialize_dup, Kernel#iterator?, Kernel#lambda, Kernel#load, Kernel#local_variables, Kernel#loop, Kernel#open, Kernel#p, Kernel#pp, Kernel#print, Kernel#printf, Kernel#proc, Kernel#putc, Kernel#puts, Kernel#raise, Kernel#rand, Kernel#readline, Kernel#readlines, Kernel#require, Kernel#require_relative, Kernel#select, Kernel#set_trace_func, Kernel#sleep, Kernel#spawn, Kernel#sprintf, Kernel#srand, Kernel#syscall, Kernel#system, Kernel#test, Kernel#throw, Kernel#trace_var, Kernel#trap, Kernel#untrace_var, and Kernel#warn don't do anything useful with their receiver. They don't call private methods, they don't access instance variables, they in fact completely ignore what self is.

Therefore, it would be misleading if you call them like this:

foo.puts 'Hello, World!'

Because a reader would be mislead into thinking that puts does something with foo, when in fact, it completely ignores it. (This applies especially to the printing family of methods, because there also exist IO#puts and friends, which indeed do care about their receiver.)

So, in order to prevent you from misleadingly calling these methods with a receiver, they are made private, which means they can only be called without an explicit receiver. (Obviously, they will still be called on self, but at least that won't be so obvious visually.)

Technically, these aren't really methods at all, they behave more like procedures, but Ruby doesn't have procedures, so this is the best way to "fake" them.

The reason why they are also defined as singleton methods is so that you can still call them in contexts where Kernel is not in the inheritance hierarchy, e.g. something like this:

class Foo < BasicObject
  def works
    ::Kernel.puts 'Hello, World!'
  end

  def doesnt
    puts 'Hello, World!'
  end
end

f = Foo.new

f.works
# Hello, World!

f.doesnt
# NoMethodError: undefined method `puts' for #<Foo:0x00007f97cf918ed0>

And the reason why they need to be defined separately at all is that the instance method versions are private. If they weren't, then you would simply be able to call Kernel.puts anyway, because Object includes Kernel and Kernel is an instance of Module which is a subclass of Object, thus Kernel is an indirect instance of itself. However, the methods are private and thus you would get a

NoMethodError: private method `puts' called for Kernel:Module

instead. Therefore, they need to be duplicated separately. There is actually a helper method that does that: Module#module_function. (This is also used for Math, where you can either call e.g. Math.sqrt(4) or include Math; sqrt(4). In this case, you have the choice of includeing Math or not, whereas Kernel is pre-included in Object always.)

So, in summary: the methods are duplicated as private instance methods of Kernel as well as public singleton methods (which is really just instance methods of Kernel's singleton class). The reason they are defined as private instance methods is so they cannot be called with an explicit receiver and are forced to look more like procedures. The reason they are duplicated as singleton methods of Kernel is so that they can be called with an explicit receiver as long as that explicit receiver is Kernel, in contexts where Kernel is not available in the inheritance hierarchy.

Check this out:

#ruby --disable-gems --disable-did_you_mean -e'puts Kernel.private_instance_methods(false).sort'
Array
Complex
Float
Hash
Integer
Rational
String
__callee__
__dir__
__method__
`
abort
at_exit
autoload
autoload?
binding
block_given?
caller
caller_locations
catch
eval
exec
exit
exit!
fail
fork
format
gets
global_variables
initialize_clone
initialize_copy
initialize_dup
iterator?
lambda
load
local_variables
loop
open
p
pp
print
printf
proc
putc
puts
raise
rand
readline
readlines
require
require_relative
respond_to_missing?
select
set_trace_func
sleep
spawn
sprintf
srand
syscall
system
test
throw
trace_var
trap
untrace_var
warn

"How does the method lookup find these methods at all if # doesn't show up in the ancestor chain?"

 1.class.included_modules #  => [Comparable, Kernel] 

Quoting OP:

Kernel.instance_methods.grep(/puts/) # []

As you have found yourself, private instance methods don't show up, they do with Kernel.private_instance_methods.