bedtools intersect should be the solution, but the chromosome names need to match between the files and in what you posted you have "Chr1" for one and "chr1" for the other, so it won't find any intersections as it sees those as completely separate chromosomes. With that fixed, this command should work:

bedtools intersect -a coords.bed -b genes.bed -wa -wb

The 'wa' argument means it will copy the exact start and end coordinates from the entry from file A, instead of just the coordinates of the segment that overlaps, and the 'wb' will append the entry from file B to the line so you know which gene it is intersecting. You can pipe it to the cut command to remove the gene coordinates if you don't need them:

bedtools intersect -a coords.bed -b genes.bed -wa -wb | cut -f1,2,3,7

This will result in just the entries from file A with the gene name of the overlap added. This could result in duplicate lines from file A showing up if it intersects multiple genes, so you will have to be aware of that for downstream analysis. You could use bedtools merge to convert the result back to one line per original line in file A, with a comma separated list of genes that overlapped (use the "-o distinct" argument).